Background

Due to differences in judging performance, the time limit for this problem is increased by 0.5 s.

Problem Description

Little Z is teaching himself knowledge about quantum computers. Recently, he has been studying the chapter on quantum communication and encountered an interesting problem. In this problem, Alice and Bob are doing quantum communication. Their communication language is a dictionary $S$ of size $n$. In this dictionary, each word $s_i$ ($1 \le i \le n$) can be represented by a $\boldsymbol{256}$-bit $\boldsymbol{01}$ string. In this problem, $s_i$ can be generated by calling the function gen. You can view it in gen.cpp under the problem directory. The parameters n, a1, and a2 of this function will be given by the input.

Alice and Bob will then communicate $m$ times. In each communication, Alice transmits exactly one word from the dictionary to Bob. However, the channel they use is unreliable and will be affected by noise. More specifically, for the $i$-th transmission, let the original word transmitted by Alice be $x_i$. This $01$ string will be affected by noise and have at most $\boldsymbol{k_i}$ bits flipped. In other words, let the $01$ string received by Bob this time be $y_i$. Compared with $x_i$, it may differ in up to $k_i$ bits, and $y_i$ may not appear in the dictionary $S$.

At the same time, Bob learns that the bad guy Eve has also infiltrated their communication channel and is preparing to interfere with their communication. His method is to change the $01$ string received by Bob into an arbitrary $256$-bit $01$ string, and this string may not appear in the dictionary $S$. Eve is very cunning: he does not necessarily interfere with every communication.

Now Bob asks you for help. For each upcoming communication, you need to determine, based on the final $01$ string received by Bob and the noise threshold $k_i$ ($0 \le k_i \le 15$) for this communication, whether it is possible that this communication was not interfered with by Eve (that is, the $01$ string received by Bob can be obtained by flipping at most $k_i$ bits of some word in the dictionary). If it is possible that Eve did not interfere, output $1$; otherwise output $0$. Bob trusts your ability very much, so you must answer online. See the input format for the specific requirements.

To reduce input time, the string received by Bob will be given as a length $\boldsymbol{64}$ hexadecimal string. The hexadecimal string contains digit characters $\texttt{0} \sim \texttt{9}$ and uppercase letters $\texttt{A} \sim \texttt{F}$, where $\texttt{A} \sim \texttt{F}$ represent the values $10 \sim 15$ respectively.

A hexadecimal string can be converted bit by bit into a $01$ string. For example, 5 corresponds to 0101, A corresponds to 1010, and C corresponds to 1100.

Input Format

The first line contains four non-negative integers $n, m, a_1, a_2$, representing the dictionary size, the number of communications, and the initial values of parameters a1 and a2 in the gen function.

You need to call the gen function mentioned in the description in your program to generate the dictionary. You may copy and use the code in gen.cpp. The boolean array s[N+1][256] in the program contains all words.

In the next $m$ lines, each line contains a hexadecimal string of length $64$ and a non-negative integer $k_i$, representing the $01$ string finally received by Bob in the $i$-th communication and the noise threshold.

To force contestants to answer queries online, after restoring the 256-bit $01$ string from the hexadecimal string, you must XOR each bit of the $01$ string with ${\mathit{lastans}}$ to obtain the real $01$ string received by Bob in this communication, where ${\mathit{lastans}} \in \{ 0, 1 \}$ is the answer to the previous query. Before the first query, ${\mathit{lastans}}$ is initialized to 0.

Note: When using scanf and printf to read or output variables of type unsigned long long, the corresponding format specifier is llu.

Output Format

Output $m$ lines. Each line contains an integer $0$ or $1$ indicating the answer to the current query.

见附件中的 qi/qi1.in

见附件中的 qi/qi1.ans

见附件中的 qi/qi2.in

见附件中的 qi/qi2.ans

见附件中的 qi/qi3.in

见附件中的 qi/qi3.ans

Hint

[Query Example]

To make the statement easier to explain, we give an example in a simplified setting by directly providing the words in the dictionary, reducing the word length to 4, and allowing offline queries.

Consider a dictionary of size $n = 2$, with words 1010 and 0111.

For the query B = 1011 and $k_1 = 1$, the answer should be $1$, because it can be obtained by flipping the 4-th bit of 1010 (from high to low bits, same below).

For the query 1 = 0001 and $k_2 = 2$, the answer should be $1$, because it can be obtained by flipping the 2-nd and 3-rd bits of 0111.

For the query 1 = 0001 and $k_3 = 1$, the answer should be $0$.

• By flipping at most 1 bit of 1010, we can obtain 1010, 0010, 1110, 1000, 1011.
• By flipping at most 1 bit of 0111, we can obtain 0111, 1111, 0011, 0101, 0110.
• We cannot obtain 1 = 0001, so it must be caused by Eve’s interference.

[Constraints]

For all test points: $1 \le n \le 4 \times {10}^5$, $1 \le m \le 1.2 \times {10}^5$, $0 \le k_i \le 15$, and $a_1$ and $a_2$ are uniformly randomly generated in $[0, 2^{64} - 1]$.

Translated by ChatGPT 5