RPD and Rap Sheet (Easy Version)
Contest: Codeforces Round 730 (Div. 2)
Difficulty rating: 1700
Tags: bitmasks, constructive algorithms, interactive, math

This is the easy version of the problem. The only difference is that here $$$k=2$$$. You can make hacks only if both the versions of the problem are solved.

This is an interactive problem.

Every decimal number has a base $$$k$$$ equivalent. The individual digits of a base $$$k$$$ number are called $$$k$$$-its. Let's define the $$$k$$$-itwise XOR of two $$$k$$$-its $$$a$$$ and $$$b$$$ as $$$(a + b)\bmod k$$$.

The $$$k$$$-itwise XOR of two base $$$k$$$ numbers is equal to the new number formed by taking the $$$k$$$-itwise XOR of their corresponding $$$k$$$-its. The $$$k$$$-itwise XOR of two decimal numbers $$$a$$$ and $$$b$$$ is denoted by $$$a\oplus_{k} b$$$ and is equal to the decimal representation of the $$$k$$$-itwise XOR of the base $$$k$$$ representations of $$$a$$$ and $$$b$$$. All further numbers used in the statement below are in decimal unless specified. When $$$k = 2$$$ (it is always true in this version), the $$$k$$$-itwise XOR is the same as the bitwise XOR.

You have hacked the criminal database of Rockport Police Department (RPD), also known as the Rap Sheet. But in order to access it, you require a password. You don't know it, but you are quite sure that it lies between $$$0$$$ and $$$n-1$$$ inclusive. So, you have decided to guess it. Luckily, you can try at most $$$n$$$ times without being blocked by the system. But the system is adaptive. Each time you make an incorrect guess, it changes the password. Specifically, if the password before the guess was $$$x$$$, and you guess a different number $$$y$$$, then the system changes the password to a number $$$z$$$ such that $$$x\oplus_{k} z=y$$$. Guess the password and break into the system.

Input format:
The first line of input contains a single integer $$$t$$$ ($$$1\leq t\leq 10\,000$$$) denoting the number of test cases. $$$t$$$ test cases follow.

The first line of each test case contains two integers $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$) and $$$k$$$ ($$$k=2$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Interaction format:
For each test case, first read two integers $$$n$$$ and $$$k$$$. Then you may ask up to $$$n$$$ queries.

For each query, print a single integer $$$y$$$ ($$$0\leq y\leq 2\cdot 10^7$$$). Let the current password be $$$x$$$. After that, read an integer $$$r$$$.

If $$$x=y$$$, you will read $$$r=1$$$ and the test case is solved. You must then continue solving the remaining test cases.

Else, you will read $$$r=0$$$. At this moment the password is changed to a number $$$z$$$ such that $$$x\oplus_{k} z=y$$$.

After printing a query, do not forget to output the end of line and flush the output. Otherwise, you will get the Idleness limit exceeded verdict.

To do this, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.

If you ask an invalid query or exceed $$$n$$$ queries, you will read $$$r=-1$$$ and you will receive the Wrong Answer verdict. Make sure to exit immediately to avoid unexpected verdicts.

Note that the interactor is adaptive. That is, the original password is not fixed in the beginning and may depend on your queries. But it is guaranteed that at any moment there is at least one initial password such that all the answers to the queries are consistent.

Hacks:

To use hacks, use the following format of tests:

The first line should contain a single integer $$$t$$$ ($$$1\leq t\leq 10\,000$$$) — the number of test cases.

The first and only line of each test case should contain two integers $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$) and $$$k$$$ ($$$k=2$$$) denoting the number of queries and the base respectively. The optimal original password is automatically decided by the adaptive interactor.

You must ensure that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
In the example test case, the hidden password is $$$2$$$.

The first query is $$$3$$$. It is not equal to the current password. So, $$$0$$$ is returned, and the password is changed to $$$1$$$ since $$$2\oplus_2 1=3$$$.

The second query is $$$4$$$. It is not equal to the current password. So, $$$0$$$ is returned, and the password is changed to $$$5$$$ since $$$1\oplus_2 5=4$$$.

The third query is $$$5$$$. It is equal to the current password. So, $$$1$$$ is returned, and the job is done.

Note that this initial password is taken just for the sake of explanation. When you submit, the interactor might behave differently because it is adaptive.

Example input:
1
5 2

0

0

1

Example output:
3

4

5

Editorial:
In this version of the problem, $$$k=2$$$. So, the $$$k$$$-itwise XOR is the same as Bitwise XOR.
In case of incorrect guess, the system changes password to $$$z$$$ such that $$$x\oplus z=y$$$. Taking XOR with $$$x$$$ on both sides, $$$x\oplus x\oplus z=x\oplus y\implies z=x\oplus y$$$ because we know that $$$x\oplus x = 0$$$.
Since the original password is less than $$$n$$$ and we have $$$n$$$ queries, we need to find a way to make queries such that if the original password was $$$x$$$, then the $$$(x+1)$$$-th query will be equal to the current password. There are many different approaches. I will describe two of them.
Solution 1 -
Let $$$q_i$$$ denote the $$$i$$$-th query. Then,
• $$$q_1=0$$$.
• $$$q_i=(i-1)\oplus (i-2)$$$ for $$$2\leq i\leq n$$$.
Let's see why this works.
Claim - If the original password was $$$x$$$, after $$$i$$$ queries, the current password will be $$$x\oplus (i-1)$$$.
Proof - Let's prove this by induction.
Base Condition - After $$$1$$$-st query, the password becomes $$$x\oplus 0=x\oplus(1-1)$$$.
Induction Hypothesis - Let the password after $$$i$$$-th query be $$$x\oplus (i-1)$$$.
Inductive step - The $$$(i+1)$$$-th query will be $$$i\oplus(i-1)$$$. If this is not equal to the current password, the password will change to $$$(x\oplus(i-1))\oplus(i\oplus(i-1))$$$ $$$=x\oplus(i-1)\oplus i\oplus(i-1)$$$ $$$=x\oplus i$$$ $$$=x\oplus((i+1)-1)$$$.
Hence, proved by induction.
Now notice that after $$$x$$$ queries, the password will become $$$x\oplus(x-1)$$$. And our $$$(x+1)$$$-th query will be $$$x\oplus(x-1)$$$ which is the same as the current password. So, the problem will be solved after $$$(x+1)$$$ queries. Since $$$0\leq x < n$$$, the problem will be solved in at most $$$n$$$ queries.
Solution 2 (Idea by KAN) -
Again, let $$$q_i$$$ denote the $$$i$$$-th query. Then,
$$$q_i=(i-1)\oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{i-2} \oplus q_{i-1}$$$
Let's see why this works.
Claim - If the original password was $$$x$$$, after $$$i$$$ queries, the current password will be $$$x \oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{i-1} \oplus q_{i}$$$.
Proof - Let's prove this by induction.
Base Condition - The first query is $$$0$$$. After $$$1$$$-st query, the password becomes $$$x\oplus 0=x\oplus q_1$$$.
Induction Hypothesis - Let the password after $$$i$$$-th query be $$$x \oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{i-1} \oplus q_{i}$$$.
Inductive step - The $$$(i+1)$$$-th query will be $$$q_{i+1}$$$. So, the password after $$$(i+1)$$$-th query will be $$$(x \oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{i-1} \oplus q_{i})\oplus q_{i+1}$$$ $$$= x \oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{i-1} \oplus q_{i}\oplus q_{i+1}$$$.
Hence, proved by induction.
Now notice that after $$$x$$$ queries, the password will become $$$x \oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{x-1} \oplus q_{x}$$$. And our $$$(x+1)$$$-th query will be $$$x \oplus q_1 \oplus q_2 \oplus \ldots \oplus q_{x-1} \oplus q_{x}$$$ which is the same as the current password. So, the problem will be solved after $$$(x+1)$$$ queries. Since $$$0\leq x < n$$$, the problem will be solved in at most $$$n$$$ queries.
But we are not done yet. We can't afford to calculate the value of each query naively in $$$\mathcal{O}(n)$$$ because this will time out. To handle this, we need to maintain a prefix XOR whose value will be $$$p=q_1\oplus q_2\oplus \ldots \oplus q_{i-1} \oplus q_i$$$ after $$$i$$$ queries. For the $$$(i+1)$$$-th query, find $$$q_{i+1}=p\oplus i$$$ and update $$$p=p\oplus q_{i+1}$$$.
Time Complexity - $$$\mathcal{O}(n)$$$ or $$$\mathcal{O}(n\cdot \log_{2} n)$$$ depending upon the implementation.