题目描述

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

Alice 和 Bob 接下来要进行 $m$ 次通信，每次通信由 Alice 向 Bob 传输恰好一个字典中的单词。然而，两人使用的通信信道并不可靠，会受到噪音的干扰。更具体地，对 于第 $i$ 次传输，记 Alice 传输的原单词为 $x_i$，该 $\text{01}$ 串会受噪音干扰而 翻转最多 $k_i$ 位。

换句话说，记 Bob 这次收到的 $\text{01}$ 串为 $y_i$，它与 $x_i$ 相比，可能有最多 $k_i$ 位是不同的，并且 $y_i$ 可能不在字典 $S$ 中出现。

与此同时，Bob 得知坏人 Eve 也潜入了两人的通信信道，并准备干扰两人的通信。

他的干扰方式是将 Bob 收到的 $\text{01}$ 串变为任意的 $256$ 位 $\text{01}$ 串，并且这个串可能不在字典 $S$ 中出现。Eve 非常狡猾，他不一定会对每次通信都进行干扰。

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

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

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

输入格式

从文件 qi.in 中读入数据。

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

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

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

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

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

输出格式

输出到文件 qi.out 中。 输出共 $m$ 行，每行一个整数 $0$ 或 $1$ 表示当前询问的答案。

询问举例

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

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

对于询问 $\text{B = 1011}$ 和 $k_1 = 1$，回答应该是 1，通过翻转 $\text{1010}$ 的第 $4$ 位（从高位到低位，下同）得到。
对于询问 $\text{1 = 0001}$ 和 $k_2 = 2$，回答应该是 1，通过翻转 $\text{0111}$ 的第 $2,3$ 位得到。
对于询问 $\text{1 = 0001}$ 和 $k_3 = 1$，回答应该是 0。

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

样例 1

见选手目录下的 qi1.in 与 qi1.ans。

样例 2

见选手目录下的 qi2.in 与 qi2.ans。

样例 3

见选手目录下的 qi3.in 与 qi3.ans。

数据规模与约定

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

测试点编号	$n =$	$m =$	$k_i\le$	特殊性质
$1$	$10$		$2$	无
$2$	$500$		$15$
$3$	$10^3$		$0$
$4$	$2\times 10^3$		$2$
$5$	$5\times10^3$	$5\times 10^3$	$15$
$6$	$10^4$
$7$	$20\times 10^4$	$2\times 10^4$
$8$	$10^5$		$1$
$9$	$4\times 10^5$	$1.2\times 10^5$
$10$	$5\times 10^4$		$2$
$11$	$7\times 10^4$		$3$
$12$	$1\times 10^5$		$2$
$13$	$3\times 10^4$		$5$
$14$	$6\times 10^4$		$4$
$15$	$1.2\times 10^5$		$5$
$16$	$6\times 10^4$		$8$	所有询问串随机生成
$17$	$1.2\times 10^5$		$12$
$18$	$4\times 10^5$	$10^5$	$15$
$19$	$3\times 10^4$		$7$	无
$20$	$6\times 10^4$		$9$
$21$	$9\times 10^4$		$11$
$22$	$2\times 10^5$	$1.2\times 10^5$	$12$
$23$	$4\times 10^5$	$8\times 10^4$	$15$
$24$		$1\times 10^5$
$25$		$1.2\times 10^5$