Problem Background

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

Problem Description

Xiao Z is self-studying quantum computer-related knowledge, and recently he encountered an interesting problem in the quantum communication section. In this problem, Alice and Bob are conducting quantum communication, using a dictionary \( S \) of size \( n \). Each word \( s_i \) ( \( 1 \le i \le n \) ) in this dictionary can be represented by a 256-bit binary string. In this problem, \( s_i \) can be generated by calling the function gen, which can be viewed in gen.cpp in the problem directory. The parameters \( n \), \( a1 \), and \( a2 \) for this function will be provided by the input data.

Alice and Bob will conduct \( m \) communications, each time transmitting exactly one word from the dictionary. However, the communication channel they use is unreliable and subject to noise interference. Specifically, for the \( i \)-th transmission, let the original word transmitted by Alice be \( x_i \). This binary string may be flipped at most \( k_i \) bits due to noise. In other words, let the binary string received by Bob be \( y_i \). It may differ from \( x_i \) by at most \( k_i \) bits, and \( y_i \) may not appear in the dictionary \( S \).

At the same time, Bob knows that the villain Eve has infiltrated their communication channel and is preparing to interfere with their communication. Eve's interference method is to change the binary string received by Bob into any 256-bit binary string, which may not appear in the dictionary \( S \). Eve is very cunning and may not interfere with every communication.

Now, Bob has asked you for help. For each subsequent communication, you need to determine based on the final binary string received by Bob and the noise interference threshold \( k_i \) ( \( 0 \le k_i \le 15 \) ) whether this communication could have been unaffected by Eve's interference (i.e., whether the binary string received by Bob could be obtained by flipping at most \( k_i \) bits from any word in the dictionary). If this communication could have been unaffected by Eve's interference, output \( 1 \); otherwise, output \( 0 \). You need to answer the results online, as specified in the input format.

To reduce input time, the string received by Bob will be given as a 64-length hexadecimal string, which includes numeric characters 0 to 9 and uppercase English letters A to F, where characters A to F represent values 10 to 15 respectively.

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

Input Format

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

The contestant needs to call the gen function described in the problem to generate the word list. The contestant can copy and use the code from gen.cpp, and the boolean array s[N+1][256] in the program is the set of all words.

The next \( m \) lines each contain a 64-length hexadecimal string and a non-negative integer \( k_i \), representing the binary string received by Bob in the \( i \)-th communication and the noise interference threshold.

To force contestants to answer queries online, after converting the hexadecimal string to a 256-bit binary string, each bit of the binary string should be XORed with \( \mathit{lastans} \) to obtain the actual binary string received by Bob in this communication, where \( \mathit{lastans} \in \{ 0, 1 \} \) represents the answer to the previous query, and \( \mathit{lastans} \) is initially 0 for the first query.

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

Output Format

The output consists of \( m \) lines, each containing an integer \( 0 \) or \( 1 \) representing the answer to the current query.

Sample Input and Output

Input Sample #1

See attachment qi/qi1.in

Output Sample #1

See attachment qi/qi1.ans

Input Sample #2

See attachment qi/qi2.in

Output Sample #2

See attachment qi/qi2.ans

Input Sample #3

See attachment qi/qi3.in

Output Sample #3

See attachment qi/qi3.ans

Notes/Hints

[Example of Queries]

To facilitate the explanation of the problem, we have used a simplified scenario where the words in the dictionary are directly given, the word length is reduced to 4, and the queries can be answered offline.

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 \), obtained by flipping the 4th bit of 1010.

For the query 1 = 0001 and \( k_2 = 2 \), the answer should be \( 1 \), obtained by flipping the 2nd and 3rd bits of 0111.

For the query 1 = 0001 and \( k_3 = 1 \), the answer should be \( 0 \).

• Flipping at most 1 bit from 1010 can result in 1010, 0010, 1110, 1000, 1011.
• Flipping at most 1 bit from 0111 can result in 0111, 1111, 0011, 0101, 0110.
• 1 = 0001 cannot be obtained, it must have been interfered with by Eve.

[Data Range]

For all test cases: \( 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 \) and \( a_2 \) are uniformly randomly generated within the range \([0, 2^{64} - 1]\).

见题面 Input 部分

见题面 Output 部分