Xiao Z is self-studying knowledge related to quantum computers. Recently, he has been researching the chapter on quantum communication and encountered an interesting problem. In this problem, Alice and Bob are performing quantum communication. Their communication language is a dictionary $S$ of size $n$, where each word $s_i$ ($1 \le i \le n$) can be represented by a 256-bit binary string. In this problem, $s_i$ can be generated by calling the function gen, which the contestant can view in gen.cpp within the problem directory. The parameters $n$, $a_1$, and $a_2$ for this function will be provided in the input data.

Alice and Bob are about to perform $m$ communications, where each communication consists of Alice transmitting exactly one word from the dictionary to Bob. However, the communication channel they use is unreliable and subject to noise interference. More specifically, for the $i$-th transmission, let the original word transmitted by Alice be $x_i$. This binary string is subject to noise interference that flips at most $k_i$ bits.

In other words, let the binary string received by Bob be $y_i$. Compared to $x_i$, it may differ by at most $k_i$ bits, and $y_i$ may not appear in the dictionary $S$.

At the same time, Bob learns that the villain Eve has infiltrated their communication channel and is preparing to interfere with their communication. Her method of interference is to change the binary string received by Bob into an arbitrary 256-bit binary string, and this string may not appear in the dictionary $S$. Eve is very cunning; she does not necessarily interfere with every communication.

Now, Bob has asked for your help. For each subsequent communication, you need to determine whether it is possible that the communication was not interfered with by Eve (i.e., the binary string received by Bob can be obtained by flipping at most $k_i$ bits of some word in the dictionary), based on the binary string Bob finally received and the noise interference threshold $k_i$ ($0 \le k_i \le 15$) for this communication. If it is possible that the communication was not interfered with by Eve, output 1; otherwise, output 0. Bob trusts your ability, so you need to answer the results online. See the Input section for specific requirements.

To reduce input time, the string received by Bob will be given as a 64-character hexadecimal string. The hexadecimal string contains numeric characters $0 \sim 9$ and uppercase English letters $A \sim F$, where characters $A \sim F$ represent values $10 \sim 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$, and $C$ corresponds to $1100$.

Input

Read data from the file qi.in.

The first line of the input 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 $a_1$ and $a_2$ in the gen function, respectively.

Contestants need to call the gen function mentioned in the problem description in their own programs to generate the word list. Contestants can copy and use the code in gen.cpp. The boolean array s[N+1][256] in the program represents all the words.

Next, there are $m$ lines, each containing a 64-character hexadecimal string and a non-negative integer $k_i$, representing the binary string Bob finally received and the noise interference threshold for the $i$-th communication, respectively.

To force contestants to answer queries online, after the contestant restores the 256-bit binary string from the hexadecimal string, they must XOR each bit of the binary string with $lastans$ to obtain the true binary string received by Bob in this communication, where $lastans \in \{0, 1\}$ represents the answer to the previous query. For the first query, the initial value of $lastans$ is $0$.

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

Output

Output to the file qi.out.

Output a total of $m$ lines, each containing an integer $0$ or $1$ representing the answer to the current query.

Examples

Input 1

(See qi/qi1.in in the contestant directory)

Output 1

(See qi/qi1.ans in the contestant directory)

Input 2

(See qi/qi2.in in the contestant directory)

Output 2

(See qi/qi2.ans in the contestant directory)

Input 3

(See qi/qi3.in in the contestant directory)

Output 3

(See qi/qi3.ans in the contestant directory)

Constraints

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