题目描述

小 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$ 表示当前询问的答案。

询问举例

为了方便解释题意，我们使用了直接给出字典中单词、缩小单词长度为 $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 干扰得到的。

样例下载

http://119.27.163.117/download.php?type=problem&id=94

gen.cpp

#include <cstdio>

typedef unsigned long long ull;
const int N = 400000;
bool s[N+1][256];

ull myRand(ull &k1, ull &k2) {
    ull k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= (k3 << 23);
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}

void gen(int n, ull a1, ull a2) {
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 256; j++)
            s[i][j] = (myRand(a1, a2) & (1ull << 32)) ? 1 : 0;
}

int main() {
    return 0;
}

数据范围

考虑到 InfOJ 和 NOI 现场评测机的速度差异，时限放大至 3s。

对于所有测试点：$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]$ 之间均匀随机生成。