Quantum Communication Noise

Alice and Bob are communicating using a quantum channel with a dictionary \(S\) of \(n\) words. Each word \(s_i\) (\(1 \le i \le n\)) is represented by a 256‐bit binary string. The dictionary \(S\) is generated via a pseudorandom procedure gen(n, a1, a2) (its implementation is available in gen.cpp).

They then perform \(m\) communications. In each communication, Alice sends exactly one word from \(S\). However, due to channel noise, the transmitted 256‐bit string \(x_i\) may have up to \(k_i\) bits flipped, resulting in Bob receiving a string \(y_i\). Note that the received \(y_i\) (provided as a 64–character hexadecimal string; each hex digit converts to 4 bits) might not even be in \(S\).

Additionally, an adversary Eve may tamper with Bob’s received string by arbitrarily modifying it. Bob asks you to decide, for each communication, whether it is possible that no tampering by Eve occurred. In other words, you must check if there exists some word \(s \in S\) such that the Hamming distance between \(s\) and \(y_i\) is at most \(k_i\) (i.e. \(\mathrm{d_H}(s, y_i) \le k_i\)). If such a word exists, output 1; otherwise, output 0.

Note on Representation: The received 256–bit string is given as a 64–character hexadecimal string. For example, the hex digit 5 corresponds to the binary 0101 and A corresponds to 1010.

Mathematical Formulations:

• Dictionary size: \(n\).
• Word representation: 256–bit binary string.
• Noise constraint in the \(i\)th transmission: \(\mathrm{d_H}(x_i,y_i) \le k_i\) if no Eve interference occurred.

Please answer the queries in an online manner (i.e. process each query as it comes and output the answer immediately).

inputFormat

The input begins with a line containing three integers \(n\), \(a1\), and \(a2\), which are used to generate the dictionary \(S\) using the provided function gen.

The next line contains a single integer \(m\), the number of communications.

Then, \(m\) lines follow. Each line contains a 64–character hexadecimal string (representing the 256–bit received string \(y_i\)) and an integer \(k_i\) (with \(0 \le k_i \le 15\)), separated by space.

Note: You must process the queries online.

outputFormat

For each of the \(m\) transmissions, output a single line containing 1 if there exists a word in \(S\) whose Hamming distance with the received string is at most \(k_i\), and 0 otherwise.

sample

1 0 0
3
0000000000000000000000000000000000000000000000000000000000000000 0
0000000000000000000000000000000000000000000000000000000000000000 1
F000000000000000000000000000000000000000000000000000000000000000 3

1
1
0