This is an interactive problem.

Alice and Bob are playing a guessing game. First, Alice chooses $b \in \{0, 1\}$, and Bob does not know the value of $b$. Then, Alice generates a permutation on $\{0, 1\}^{64}$ as follows:

• If $b=0$, $P$ is chosen uniformly at random from all permutations on $\{0, 1\}^{64}$.
• If $b=1$:
  • $f_1, f_2, f_3$ are chosen independently and uniformly at random from all functions $\{0, 1\}^{32} \to \{0, 1\}^{32}$.
  • To calculate $P(x)$, Alice first splits $x$ into $x = x_0 \circ x_1$, where $x_0$ and $x_1$ are each 32 bits long.
  • Alice performs the following calculations:
    • $x_2 = x_0 \oplus f_1(x_1)$
    • $x_3 = x_1 \oplus f_2(x_2)$
    • $x_4 = x_2 \oplus f_3(x_3)$
  • Alice outputs $x_3 \circ x_4$ as $P(x)$. In other words, $P(x_0 \circ x_1) = x_3 \circ x_4$, where $x_3$ and $x_4$ are defined as above.

It is easy to see that in both cases, the resulting $P$ is a well-defined permutation. Now, Bob needs to determine the value of $b$. He can make the following two types of queries to Alice:

• Bob chooses any $x \in \{0, 1\}^{64}$ and queries $P(x)$.
• Bob chooses any $x \in \{0, 1\}^{64}$ and queries $P^{-1}(x)$.

Since Alice is in a hurry to meet a deadline, she requires Bob to make no more than 256 queries. However, Bob is not good at dealing with randomized problems, so he has come to you for help. Please help Bob design an algorithm to correctly guess $b$.

Interaction

This problem only supports c++. You should include interaction.h (see the provided files) in your submitted source file. The interface functions for interaction are defined as follows:

/**
 * @brief Queries P(x) or P^{-1}(x)
 * @param x The value to query
 * @param rev Set rev=0 to query P(x), rev=1 to query P^{-1}(x)
 * @return P(x) for rev=0, P^{-1}(x) for rev=1
 */
unsigned long long getperm(unsigned long long x,int rev);
/**
 * @brief Make no more than 256 calls to getperm, to guess b
 * @see getperm
 * @return The b you guesses
 */
int guessb();

You should implement int guessb() in your source file. It should make no more than 256 queries by calling getperm and return $0/1$ as its guess for $b$. If anything is unclear, permutation.cpp in the provided files is a simple implementation that you can modify to create your source file.

Compilation & Execution

Use

g++ -o grader grader.cpp permutation.cpp

to compile your source file with the interaction library to obtain the executable grader. Here, permutation.cpp is your local source file name.

Then, for Linux/MacOS, use

./grader

to run; for Windows, use

grader.exe

to run.

Input

Each test case contains multiple data sets.

The first line contains a positive integer $t$, representing the number of data sets.

The second line contains two 64-bit unsigned integers $s_0, s_1$ ($0 \le s_0, s_1 \le 2^{64}-1$), representing the random seed used by the grader.

This is the job of grader.cpp. You should not read any data from standard input in your submitted source file.

Output

Output one line for each data set. If more than 256 queries are made, output QLE. Otherwise, if the guess for $b$ is correct, output OK; if the guess is incorrect, output WA.

This is the job of grader.cpp. You should not write any data to standard output in your submitted source file.

Constraints

For 20% of the test cases, $t=1$.

For another 20% of the test cases, $t=4$.

For the remaining 60% of the test cases, $t=100$.

We guarantee that the total time required for the grader.cpp on the OJ to process 25,600 queries does not exceed 10ms.

Regarding the representation of binary strings as integers: We define that the least significant bit of the integer corresponds to the first binary character, and the most significant bit corresponds to the last binary character. Therefore, for $x = x_0 \circ x_1$, $x_0$ is the lower 32 bits of $x$, and $x_1$ is the upper 32 bits of $x$. For example, for x=0xFEDCBA9876543210, we have x_0=0x76543210 and x_1=0xFEDCBA98. The same applies to $x_3 \circ x_4$.

Note

The provided grader.cpp is for reference only. When evaluating on the OJ, we will use a different grader.cpp (guaranteed to have the same interface functionality). Your submitted source file should only access the interfaces provided in interaction.h and should not attempt to access the internals of grader.cpp.