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$$$.

Input

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.

Interaction

First, you need to output a single integer $$$x \, (0 \le x \lt 2^{30})$$$ — the initial value to send to the interactor.

In response, you will receive a single integer $$$o\,(0 \le o \lt 2^{30})$$$ — the result $$$o(v,x)$$$ of the operation $$$v\,\mathrm{ty}\,x.$$$

Next, you will send a single line containing two integers $$$m_0, m_1\,(0 \le m_0, m_1 \lt 2^{30}).$$$

Finally, receive a single integer $$$r\,(0 \le r \lt 2^{30})$$$ — the value of $$$m_b \oplus v.$$$

Note that the interactor is partially adaptive — in particular, the choice of $$$v$$$ may be determined by the initial input $$$x$$$, but all hidden values will be fixed after.

After printing each query do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict.

If, at any interaction step, you read $$$-1$$$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

$$$^{\text{∗}}$$$To flush, use:

fflush(stdout) or cout.flush() in C++;
sys.stdout.flush() in Python;
see the documentation for other languages.

Note

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$$$	$$$\|$$$

lce4113 and Security Game

Examples