题目描述

小 Z 正在自学量子计算机相关知识，最近他在研究量子通信章节，并遇到了一个有趣的问题。在该问题中，Alice 和 Bob 正在进行量子通信，它们的通信语言是一个大小为 $n$ 的字典 $S$，在该字典中，每一个单词 $s_i$（$1 \le i \le n$）都可以用一个 $256$ 位的 $01$ 串来表示。在本题中 $s_i$ 可以通过调用函数 gen 来生成，选手可以在题目目录下的 gen.cpp 中查看，该函数的参数 $n$、$a_1$、$a_2$ 将由输入数据给出。

Alice 和 Bob 接下来要进行 $m$ 次通信，每次通信由 Alice 向 Bob 传输恰好一个字典中的单词。然而，两人使用的通信信道并不可靠，会受到噪音的干扰。更具体地，对于第 $i$ 次传输，记 Alice 传输的原单词为 $x_i$，该 $01$ 串会受噪音干扰而翻转最多 $k_i$ 位。换句话说，记 Bob 这次收到的 $01$ 串为 $y_i$，它与 $x_i$ 相比，可能有最多 $k_i$ 位是不同的，并且 $y_i$ 可能不在字典 $S$ 中出现。

与此同时，Bob 得知坏人 Eve 也潜入了两人的通信信道，并准备干扰两人的通信。他的干扰方式是将 Bob 收到的 $01$ 串变为任意的 $256$ 位 $01$ 串，并且这个串可能不在字典 $S$ 中出现。Eve 非常狡猾，他不一定会对每次通信都进行干扰。

现在 Bob 找来了你帮忙，对于接下来的每次通信，你需要根据 Bob 最终收到的 $01$ 串以及这次通信的噪音干扰阈值 $k_i$（$0 \le k_i \le 15$），判断这次通信是否有可能没有受到 Eve 的干扰（即 Bob 收到的 $01$ 串可以由字典中的某个单词翻转至多 $k_i$ 位后得到）。本次通信如果有可能没受到 Eve 干扰，请你输出 $1$，否则输出 $0$。Bob 很信任你的能力，所以你需要在线地回答结果，具体要求见输入格式。

为了降低读入用时， Bob 收到的串将用长度为 $64$ 的 $16$ 进制串给出，$16$ 进制串中包含数字字符 $\texttt{0} \sim \texttt{9}$ 与大写英文字母 $\texttt{A} \sim \texttt{F}$，其中字符 $\texttt{A} \sim \texttt{F}$ 依次表示数值 $10 \sim 15$。

$16$ 进制串可以逐位转化为 $01$ 串，例如：$\texttt{5}$ 对应 $0101$，$\texttt{A}$ 对应 $1010$，$\texttt{C}$ 对应 $1100$。

输入格式

从文件 qi.in 读入数据。

输入数据第一行包含四个非负整数 $n$, $m$, $a_1$, $a_2$，分别表示字典大小，通信次数，以及 gen 函数中参数 a1 和 a2 的初始值。

选手需要在自己的程序中调用题目描述中提到的 gen 函数生成单词表，选手可以复制并使用 gen.cpp 中的代码，程序中的布尔数组 s[N+1][256] 即为所有的单词。

接下来 $m$ 行，每行包含一个长度为 $64$ 的 $16$ 进制串和一个非负整数 $k_i$，分别表示第 $i$ 次通信 Bob 最终收到的 $01$ 串和噪音干扰阈值。

为了强制选手在线地回答询问，选手根据 $16$ 进制串还原出 $256$ 位 $01$ 串后，将 $01$ 串每一位异或上 $\mathit{lastans}$ 才能得到这次通信中 Bob 收到的真实 $01$ 串，其中 $\mathit{lastans} \in { 0, 1 }$ 表示上一次询问的答案，第一个询问前 $\mathit{lastans}$ 初始值为 $0$。

注意：使用 scanf 和 printf 函数读入或输出 unsigned long long 类型变量时，对应的占位符为 %llu。

输出格式

输出到文件 qi.out 中。

输出共 $m$ 行，每行一个整数 $0$ 或 $1$ 表示当前询问的答案。

10 10 155719172195742742 2592928081197251992
2AAE5EEC8A9CEA1C618616431B5CBBCD5FEEC794B4BCC4EA568204B9C965406D 4
A6C5B9900DA278E04C5080DCA5D9C6B2F2D7C063290B33C453B6B8B9723AD262 2
2AAE5EEC8A9CEA0C61A616431B5CBBCD5FEEC794B4BCC4EA568204BBC9654065 3
91FF221DEAA1D2ABA4DAB6E512EADA803061D7B0ECCFC9FA207B50A7ADC8AC1B 5
4BCD4F789A68C04B1F57E6C733E5465DC304BB4B011174F6A46FFC98A340250E 5
B432B08765971FB4E0A81938CC1AB9A23CFB44B4FEEE8B095B9003675CBFDAF1 5
516BD2BE89A6C6B1E072DF7139143F9F61C029421576E8915DF109E9616C919B 2
AE942D417659394E1F8D208EC6FBC0609E3FD6BDEA89176EA20AF6169E936E64 5
2AAE5EEC8A9CEA0C61A616431B5CBBCD5FEEC794B4BCC4EA568204BBC96D4065 2
A6C5B9900DA278E04C5080DCA5D9C6B2F297C063290B33C453B6B8B9723AD262 5

0
1
1
0
1
1
0
0
0
1

询问举例

为了方便解释题意，我们使用了直接给出字典中单词、缩小单词长度为 $4$、允许离线地回答询问等方式，对简化的情况举例。

考虑字典大小为 $n = 2$，单词有 $1010$ 和 $0111$。

对于询问 $B = 1011$ 和 $k_1 = 1$，回答应该是 $1$，通过翻转 $1010$ 的第 $4$ 位（从高位到低位，下同）得到。

对于询问 $1 = 0001$ 和 $k_2 = 2$，回答应该是 $1$，通过翻转 $0111$ 的第 $2$、$3$ 位得到。

对于询问 $1 = 0001$ 和 $k_3 = 1$，回答应该是 $0$。

翻转 $1010$ 至多 $1$ 位可得 $1010$、$0010$、$1110$、$1000$、$1011$。 翻转 $0111$ 至多 $1$ 位可得 $0111$、$1111$、$0011$、$0101$、$0110$。 无法得到 $1 = 0001$，它必定是由 Eve 干扰得到的。

数据规模与约定

对于所有测试点：$1 \le n \le 4 \times {10}^5$，$1 \le m \le 1.2 \times {10}^5$，$0 \le k_i \le 15$，$a_1$ 和 $a_2$ 在 $[0, 2^{64} - 1]$ 之间均匀随机生成。