CF2246E.lce4113 and Security Game

This is an interactive problem. Additionally, hacks are disabled for this problem.

There are two hidden integers $b$ and $v$ such that $b \in {0,1}$ and $0 \le v \lt 2^{30}.$ There is also a hidden operation $\mathrm{ty},$ which is either $\&$ or $|.$ Here, $\&$ denotes the bitwise AND operation. Additionally, $|$ denotes the bitwise OR operation.

Your goal is to guess $b.$

The interaction proceeds as follows:

• First, you send a value $x$ to the interactor, such that $0 \le x \lt 2^{30}$.
• The interactor sends back $v\,\mathrm{ty}\,x$. Formally, it will send back $o(v,x)$, where $$o(v,x) = \begin{cases}v\,\&\,x & \mathrm{ty} = \& \\ v\,|\,x & \mathrm{ty} = |.\end{cases}$$
• You then send two numbers $m_0$ and $m_1$, where $0 \le m_0, m_1 \lt 2^{30}.$
• Finally, the interactor will send back $m_b \oplus v,$ where $\oplus$ denotes the bitwise XOR operation.

After the interaction, you have to output $b$.

这是一个交互式问题。此外，本题禁用 hack 功能。

存在两个隐藏整数 $b$ 和 $v$，满足 $b \in \{0,1\}$ 且 $0 \le v < 2^{30}$。还存在一个隐藏运算符 $\mathrm{ty}$，其值为 $\&$ 或 $|$。其中，$\&$ 表示按位与运算，而 $|$ 表示按位或运算。

你的目标是猜出 $b$ 的值。

交互流程如下：

• 首先，你向交互器发送一个值 $x$，满足 $0 \le x < 2^{30}$。
• 交互器返回 $v\,\mathrm{ty}\,x$。形式化地，它将返回 $o(v,x)$，其中

$$o(v,x) = \begin{cases}v\,\&\,x & \mathrm{ty} = \& \\ v\,|\,x & \mathrm{ty} = |.\end{cases}$$

• 接着，你发送两个数 $m_0$ 和 $m_1$，满足 $0 \le m_0, m_1 < 2^{30}$。
• 最后，交互器返回 $m_b \oplus v$，其中 $\oplus$ 表示按位异或运算。

交互结束后，你需要输出 $b$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows. Note that this is the only initial input given.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）。随后是测试用例的描述。注意，这是唯一给出的初始输入。

null

The example interaction proceeds as follows:

Solution

Interactor

Explanation

$3$

There are $3$ test cases.

$2$

The solution chooses $x = 2$.

$0$

The interactor sends back $x\,\mathrm{ty}\,v = 2\,\&\,1 = 0.$

$314$ $159$

The solution sends $m_0 = 314$ and $m_1 = 159.$

$315$

The interactor responds with $m_b \oplus v = m_0 \oplus v = 315.$

$0$

The solution determines $b = 0.$

$3$

The next test case begins. The solution chooses $x = 3$.

$3$

The interactor sends back $x\,\mathrm{ty}\,v = 3\,|\,1 = 3.$

$12$ $34$

The solution sends $m_0 = 12$ and $m_1 = 34.$

$35$

The interactor responds with $m_b \oplus v = m_1 \oplus v = 35.$

$1$

The solution determines $b = 1.$

$0$

The final test case begins. The solution chooses $x = 0$.

$5$

The interactor sends back $x\,\mathrm{ty}\,v = 0\,|\,5 = 5.$

$0$ $0$

The solution sends $m_0 = 0$ and $m_1 = 0.$

$5$

The interactor responds with $m_b \oplus v = m_1 \oplus v = 5.$

$1$

The solution determines $b = 1.$

Note that the queries made by the example solution may not yield enough information to determine the hidden bit $b.$ Additionally the empty lines in the example interaction are given for readability and need not be outputted in the solution.

The hidden values in the test cases are given below.

Test #

$v$

$b$

$\mathrm{ty}$

$1$

$1$

$0$

$\&$

$2$

$1$

$1$

$|$

$3$

$5$

$1$

$|$

示例交互过程如下：

解答

交互器

说明

$3$

共有 $3$ 个测试用例。

$2$

解答选择 $x = 2$。

$0$

交互器返回 $x\,\mathrm{ty}\,v = 2\,\&\,1 = 0$。

$314$ $159$

解答发送 $m_0 = 314$ 和 $m_1 = 159$。

$315$

交互器响应 $m_b \oplus v = m_0 \oplus v = 315$。

$0$

解答判定 $b = 0$。

$3$

下一个测试用例开始。解答选择 $x = 3$。

$3$

交互器返回 $x\,\mathrm{ty}\,v = 3\,|\,1 = 3$。

$12$ $34$

解答发送 $m_0 = 12$ 和 $m_1 = 34$。

$35$

交互器响应 $m_b \oplus v = m_1 \oplus v = 35$。

$1$

解答判定 $b = 1$。

$0$

最后一个测试用例开始。解答选择 $x = 0$。

$5$

交互器返回 $x\,\mathrm{ty}\,v = 0\,|\,5 = 5$。

$0$ $0$

解答发送 $m_0 = 0$ 和 $m_1 = 0$。

$5$

交互器响应 $m_b \oplus v = m_1 \oplus v = 5$。

$1$

解答判定 $b = 1$。

注意：示例解答所作的查询可能不足以确定隐藏比特 $b$。此外，示例交互中的空行仅为增强可读性，在实际解答中无需输出。

各测试用例中的隐藏值如下表所示：

测试编号

$v$

$b$

$\mathrm{ty}$

$1$

$1$

$0$

$\&$

$2$

$1$

$1$

$|$

$3$

$5$

$1$

$|$