[NOI2021] 量子通信

由于评测性能差异，本题时限 +0.5s。

小 Z 正在自学量子计算机相关知识，最近他在研究量子通信章节，并遇到了一个有趣的问题。在该问题中，Alice 和 Bob 正在进行量子通信，它们的通信语言是一个大小为 $n$ 的字典 $S$，在该字典中，每一个单词 $s_i$（$1 \le i \le n$）都可以用一个 $\boldsymbol{256}$ **位的** $\boldsymbol{01}$ **串**来表示。在本题中 $s_i$ 可以通过调用函数 `gen` 来生成，选手可以在题目目录下的 `gen.cpp` 中查看，该函数的参数 `n`、`a1`、`a2` 将由输入数据给出。 Alice 和 Bob 接下来要进行 $m$ 次通信，每次通信由 Alice 向 Bob 传输**恰好一个**字典中的单词。然而，两人使用的通信信道并不可靠，会受到噪音的干扰。更具体地，对于第 $i$ 次传输，记 Alice 传输的原单词为 $x_i$，该 $01$ 串会受噪音干扰而**翻转最多** $\boldsymbol{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 收到的串将用**长度为** $\boldsymbol{64}$ **的** $\boldsymbol{16}$ **进制串**给出，$16$ 进制串中包含数字字符 $\texttt{0} \sim \texttt{9}$ 与大写英文字母 $\texttt{A} \sim \texttt{F}$，其中字符 $\texttt{A} \sim \texttt{F}$ 依次表示数值 $10 \sim 15$。 $16$ 进制串可以逐位转化为 $01$ 串，例如：`5` 对应 `0101`，`A` 对应 `1010`，`C` 对应 `1100`。

输入数据第一行包含四个非负整数 $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`。

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

见附件中的 qi/qi1.in

见附件中的 qi/qi1.ans

见附件中的 qi/qi2.in

见附件中的 qi/qi2.ans

见附件中的 qi/qi3.in

见附件中的 qi/qi3.ans

**【询问举例】** 为了方便解释题意，我们使用了直接给出字典中单词、缩小单词长度为 $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]$ 之间均匀随机生成。 | 测试点编号 | $n =$ | $m =$ | $k_i \le$ | 特殊性质 | |:-:|:-:|:-:|:-:|:-:| | $1$ | $10$ | $10$ | $2$ | 无 | | $2$ | $500$ | $500$ | $15$ | 无 | | $3$ | $1000$ | $1000$ | $0$ | 无 | | $4$ | $2000$ | $2000$ | $2$ | 无 | | $5$ | $5000$ | $5000$ | $15$ | 无 | | $6$ | $10^4$ | $10^4$ | $15$ | 无 | | $7$ | $2\times 10^4$ | $2\times 10^4$ | $15$ | 无 | | $8$ | $10^5$ | $10^5$ | $1$ | 无 | | $9$ | $4\times 10^5$ | $1.2\times 10^5$ | $1$ | 无 | | $10$ | $5\times 10^4$ | $5\times 10^4$ | $2$ | 无 | | $11$ | $7\times 10^4$ | $7\times 10^4$ | $3$ | 无 | | $12$ | $10^5$ | $10^5$ | $2$ | 无 | | $13$ | $3\times 10^4$ | $3\times 10^4$ | $5$ | 无 | | $14$ | $6\times 10^4$ | $6\times 10^4$ | $4$ | 无 | | $15$ | $1.2\times 10^5$ | $1.2\times 10^5$ | $5$ | 无 | | $16$ | $6\times 10^4$ | $6\times 10^4$ | $8$ | 所有询问串随机生成 | | $17$ | $1.2\times 10^5$ | $1.2\times 10^5$ | $12$ | 所有询问串随机生成 | | $18$ | $4\times 10^5$ | $10^5$ | $15$ | 所有询问串随机生成 | | $19$ | $3\times 10^4$ | $3\times 10^4$ | $7$ | 无 | | $20$ | $6\times 10^4$ | $6\times 10^4$ | $9$ | 无 | | $21$ | $9\times 10^4$ | $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$ | $4\times 10^5$ | $10^5$ | $15$ | 无 | | $25$ | $4\times 10^5$ | $1.2\times 10^5$ | $15$ | 无 |