这是一道交互题。

Alice和Bob在玩猜数游戏。首先，Alice选择$b\in\{0,1\}$，Bob不知道$b$的值。随后Alice按照如下方式生成一个$\{0,1\}^{64}$上的排列。

• 若$b=0$，则$P$从$\{0,1\}^{64}$上的所有排列中均匀随机抽取；
• 若$b=1$：
  • $f_1,f_2,f_3$分别从$\{0,1\}^{32}\to\{0,1\}^{32}$的所有函数中独立均匀随机抽取
  • 为了计算$P(x)$，Alice首先将$x$拆分为$x=x_0\circ x_1$，$x_0,x_1$各长32bit
  • Alice进行如下的计算：
    • $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将$x_3\circ x_4$作为$P(x)$的输出。换言之，$P(x_0\circ x_1)=x_3\circ x_4$，其中$x_3,x_4$的定义方式如上

不难看出对于两种情况，得到的$P$都是一个良定义的排列。现在Bob需要确定$b$的值。他可以向Alice进行如下两种询问：

• Bob任取$x\in\{0,1\}^{64}$，并询问$P(x)$
• Bob任取$x\in\{0,1\}^{64}$，并询问$P^{-1}(x)$

由于Alice还要去赶DDL，她要求Bob只能进行不超过$256$次询问。然而Bob并不擅长应对随机化的问题，于是他来向你寻求帮助。请帮Bob设计一个算法来正确猜测$b$。

交互方式

本题仅支持c++。你应当在你提交的源文件中包含interaction.h（见下发文件）。交互所使用的接口函数定义如下：

/**
 * @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();

你应当在你的源文件中实现int guessb()。它应当通过调用getperm来进行不超过$256$次询问，并返回$0/1$作为其对$b$的猜测。如果有不清楚的地方，下发文件中的permutation.cpp是一个简易实现，你可以在其基础上进行修改得到你的源文件。

编译&运行

使用

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

来将你的源文件和交互库一起编译，并得到可执行文件grader。其中permutation.cpp是你本地的源文件名。

随后对于Linux/MacOS，使用

./grader

来运行；对于Windows，使用

grader.exe

来运行。

输入

每一个测试点包含多组数据

第一行包含一个正整数$t$，表示数据的组数

第二行包含两个64位无符号整数$s_0,s_1$（$0\le s_0,s_1\le 2^{64}-1$），代表grader所使用的随机数种子

这是grader.cpp的工作。你不应当在提交的源文件中从标准输入读取任何数据。

输出

对于每组数据输出一行。若调用了超过256次询问，则输出QLE。否则若对于$b$的猜测结果正确，则输出OK；若猜测错误，则输出WA。

这是grader.cpp的工作。你不应当在提交的源文件中向标准输出写入任何数据。

数据范围及约定

对于20%的测试点，$t=1$

对于另外20%的测试点，$t=4$

对于剩下60%的测试点，$t=100$

我们保证OJ上grader.cpp处理$25600$次询问所需总时间不超过10ms

关于用整数表示二进制字符串：我们约定整数的最低位对应第一个二进制字符，最高位对应最后一个二进制字符。因此，对于$x=x_0\circ x_1$，$x_0$是$x$的低32位，而$x_1$是$x$的高32位。例如，对于x=0xFEDCBA9876543210，我们有x_0=0x76543210以及x_1=0xFEDCBA98。对于$x_3\circ x_4$同理。

注意事项

下发的grader.cpp仅供参考。在OJ上评测时，我们会使用不同的grader.cpp（保证接口的功能相同）。你提交的源文件只能访问interaction.h中提供的接口，而不应当试图访问grader.cpp的内部。