RPD and Rap Sheet (Hard Version)
Contest: Codeforces Round 730 (Div. 2)
Difficulty rating: 2200
Tags: brute force, constructive algorithms, interactive, math

This is the hard version of the problem. The only difference is that here $$$2\leq k\leq 100$$$. 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.

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$$$ $$$(2\leq k\leq 100)$$$.

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$$$ ($$$2\leq k\leq 100$$$) 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:
Test Case 1:

In this 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.

Test Case 2:

In this case, the hidden password is $$$3$$$.

The first query is $$$1$$$. It is not equal to the current password. So, $$$0$$$ is returned, and the password is changed to $$$7$$$ since $$$3\oplus_3 7=1$$$. $$$[3=(10)_3$$$, $$$7=(21)_3$$$, $$$1=(01)_3$$$ and $$$(10)_3\oplus_3 (21)_3 = (01)_3]$$$.

The second query is $$$4$$$. It is not equal to the current password. So, $$$0$$$ is returned, and the password is changed to $$$6$$$ since $$$7\oplus_3 6=4$$$. $$$[7=(21)_3$$$, $$$6=(20)_3$$$, $$$4=(11)_3$$$ and $$$(21)_3\oplus_3 (20)_3 = (11)_3]$$$.

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

Note that these initial passwords are taken just for the sake of explanation. In reality, the grader might behave differently because it is adaptive.

Example input:
2
5 2

0

0

1
5 3

0

0

1

Example output:
3

4

5


1

4

6

Editorial:
The solutions described for the easy version won't work here because the general $$$k$$$-itwise operation does not satisfy self-inverse property, i.e., $$$a\oplus_ka\neq 0$$$.
In this whole solution, we will work in base $$$k$$$ only and we will convert the numbers to decimal only for I/O purpose. Notice that any property which is satisfied for $$$k$$$-its will also be satisfied for base $$$k$$$ numbers since a base $$$k$$$ number is nothing but a concatenation of $$$k$$$-its.
When we make an incorrect guess, the system changes the password to $$$z$$$ such that $$$x\oplus_k z=y$$$. Let's denote the $$$j$$$-th $$$k$$$-it of $$$x$$$ by $$$x_j$$$. Expanding this according to the definition of $$$k$$$-itwise XOR, for all individual $$$k$$$-its $$$(x_j+z_j)\bmod k=y_j$$$ $$$\implies z_j=(y_j-x_j)\bmod k$$$. So, let's define another $$$k$$$-itwise operation $$$a\ominus_k b$$$ $$$= (a-b)\bmod k$$$. Then, $$$z=y\ominus_k x$$$.
Solution 1 -
Before moving to the solution, let's see some properties of the $$$\ominus_k$$$ operation over $$$k$$$-its.
Property 1 - $$$(a\ominus_k b)\ominus_k(a\ominus_k c)=c\ominus_k b$$$
Proof - $$$(a\ominus_k b)\ominus_k(a\ominus_k c)$$$ $$$= ((a-b)\bmod k - (a-c)\bmod k)\bmod k$$$ $$$=(a-b-a+c)\bmod k$$$ $$$=(c-b)\bmod k$$$ $$$= c\ominus_k b$$$
Property 2 - $$$(b\ominus_k a)\ominus_k(c\ominus_k a)=b\ominus_k c$$$
Proof - $$$(b\ominus_k a)\ominus_k(c\ominus_k a)$$$ $$$= ((b-a)\bmod k - (c-a)\bmod k)\bmod k$$$ $$$=(b-a-c+a)\bmod k$$$ $$$=(b-c)\bmod k$$$ $$$= b\ominus_k c$$$
Solution -
Let $$$q_i$$$ denote the $$$i$$$-th query. Then,
• $$$q_1=0$$$,
• $$$q_i=(i-2)\ominus_k (i-1)$$$ if $$$i$$$ is even and
• $$$q_i=(i-1)\ominus_k (i-2)$$$ if $$$i$$$ is odd.
Let's see why this works.
Claim - If the original password was $$$x$$$, after $$$i$$$ queries, the password becomes
• $$$x\ominus_k (i-1)$$$ if $$$i$$$ is even and
• $$$(i-1)\ominus_k x$$$ if $$$i$$$ is odd.
Proof - Let's prove this by induction.
Base Case - $$$q_1=0$$$. So, after $$$1$$$-st query, the password becomes $$$0\ominus_k x = (1-1)\ominus_k x$$$.
Case 1 - $$$i$$$ is even
Induction hypothesis - Let the current password after $$$i$$$ queries be $$$x\ominus_k (i-1)$$$.
Inductive step - $$$(i+1)$$$ is odd. So, the $$$(i+1)$$$-th query is $$$i\ominus_k (i-1)$$$. The new password will be $$$(i\ominus_k (i-1))\ominus_k(x\ominus_k (i-1))$$$ $$$= i\ominus_k x$$$ by Property 2.
Case 2 - $$$i$$$ is odd
Induction hypothesis - Let the current password after $$$i$$$ queries be $$$(i-1)\ominus_k x$$$.
Inductive step - $$$(i+1)$$$ is even. So, the $$$(i+1)$$$-th query is $$$(i-1)\ominus_k i$$$. The new password will be $$$((i-1)\ominus_k i)\ominus_k((i-1)\ominus_k x)$$$ $$$= x\ominus_k i$$$ by Property 1.
Hence, proved by induction.
Now notice that after $$$x$$$ queries, the password will become $$$x\ominus_k (x-1)$$$ if $$$x$$$ is even or $$$(x-1)\ominus_k x$$$ if $$$x$$$ is odd which will be equal to the $$$(x+1)$$$-th query. Hence, the problem will be solved after exactly $$$(x+1)$$$ queries. Since $$$0\leq x < n$$$, the problem will be solved after at most $$$n$$$ queries.
Solution 2 -
Again, let's denote the $$$i$$$-th query by $$$q_i$$$.
Then, $$$q_i=q_{i-1}\ominus_k\bigg[q_{i-2}\ominus_k\Big[q_{i-3}\ominus_k\ldots\ominus_k\big[q_2\ominus_k[q_1\ominus_k(i-1)]\big]\ldots\Big]\bigg]$$$
Let's see why this works.
Claim - If the original password was $$$x$$$, after $$$i$$$ queries, the password will be $$$q_{i}\ominus_k\bigg[q_{i-1}\ominus_k\Big[q_{i-2}\ominus_k\ldots\ominus_k\big[q_2\ominus_k[q_1\ominus_k x]\big]\ldots\Big]\bigg]$$$
Proof - Let's prove this by induction.
Base Case - After the $$$1$$$-st query which is $$$0$$$, the password will be $$$0\ominus_k x = q_1\ominus_k x$$$.
Induction hypothesis - Let the password after $$$i$$$ queries be $$$q_{i}\ominus_k\bigg[q_{i-1}\ominus_k\Big[q_{i-2}\ominus_k\ldots\ominus_k\big[q_2\ominus_k[q_1\ominus_k x]\big]\ldots\Big]\bigg]$$$
Inductive Step - The $$$(i+1)$$$-th query is $$$q_{i+1}$$$. After $$$(i+1)$$$ queries, the password will becomes $$$q_{i+1}\ominus_k\Bigg[q_{i}\ominus_k\bigg[q_{i-1}\ominus_k\Big[q_{i-2}\ominus_k\ldots\ominus_k\big[q_2\ominus_k[q_1\ominus_k x]\big]\ldots\Big]\bigg]\Bigg]$$$
Hence, proved by induction.
Now notice that after $$$x$$$ queries, the password will become $$$q_{x}\ominus_k\bigg[q_{x-1}\ominus_k\Big[q_{x-2}\ominus_k\ldots\ominus_k\big[q_2\ominus_k[q_1\ominus_k x]\big]\ldots\Big]\bigg]$$$ which will be equal to the $$$(x+1)$$$-th query. Hence, the problem will be solved after exactly $$$(x+1)$$$ queries. Since $$$0\leq x < n$$$, the problem will be solved after at most $$$n$$$ queries.
But we are not done yet. This solution is $$$\mathcal{O}(n^2)$$$ which will time out. The solution for this isn't as simple as what we did for the Easy version because the $$$\ominus_k$$$ operation is neither associative nor commutative. So, it's time to explore some more properties of these operations.
Property 3 - $$$a\ominus_k(b\ominus_k c) = (a\ominus_k b)\oplus_k c$$$
Proof - $$$a\ominus_k(b\ominus_k c)$$$ $$$= (a-(b-c)\bmod k)\bmod k$$$ $$$= (a-b+c)\bmod k$$$ $$$= ((a-b)\bmod k+c)\bmod k$$$ $$$= (a\ominus_k b)\oplus_k c$$$
Property 4 - $$$a\ominus_k(b\oplus_k c) = (a\ominus_k b)\ominus_k c$$$
Proof - $$$a\ominus_k(b\oplus_k c)$$$ $$$= (a-(b+c)\bmod k)\bmod k$$$ $$$= (a-b-c)\bmod k$$$ $$$= ((a-b)\bmod k-c)\bmod k$$$ $$$= (a\ominus_k b)\ominus_k c$$$
Let's try to simplify our queries.
• $$$q_1=0$$$
• $$$q_2=q_1\ominus_k 1$$$
• $$$q_3=q_2\ominus_k [q_1\ominus_k 2]=[q_2\ominus_k q_1]\oplus_k 2$$$ (by Property 3)
• $$$q_4=q_3\ominus_k \big[q_2\ominus_k [q_1\ominus_k 3]\big]=q_3\ominus_k \big[[q_2\ominus_k q_1]\oplus_k 3\big]=\big[q_3\ominus_k[q_2\ominus_k q_1]\big]\ominus_k 3$$$ (by Property 4)
• $$$\ldots$$$
See the pattern?
You can generalize the $$$i$$$-th query can be simplified as -
• $$$q_i=q_{i-1}\ominus_k\Big[q_{i-2}\ominus_k\big[q_{i-3}\ominus_k\ldots\ominus_k[q_2\ominus_k q_1]\ldots\big]\Big]\oplus_k (i-1)$$$ if $$$i$$$ is odd
• $$$q_i=q_{i-1}\ominus_k\Big[q_{i-2}\ominus_k\big[q_{i-3}\ominus_k\ldots\ominus_k[q_2\ominus_k q_1]\ldots\big]\Big]\ominus_k (i-1)$$$ if $$$i$$$ is even
So, we will maintain a prefix Negative XOR whose value after $$$i$$$ queries will be $$$p=q_{i}\ominus_k\Big[q_{i-1}\ominus_k\big[q_{i-2}\ominus_k\ldots\ominus_k[q_2\ominus_k q_1]\ldots\big]\Big]$$$
Then,
• $$$q_{i+1}=p\ominus_k i$$$ if $$$i$$$ is odd
• $$$q_{i+1}=p\oplus_k i$$$ if $$$i$$$ is even
Then update $$$p=q_{i+1}\ominus_k p$$$
Notes -
1. Both the operations $$$\ominus_k$$$ and $$$\oplus_k$$$ can be implemented naively by converting the decimal numbers to base $$$k$$$, finding the $$$k$$$-itwise XOR of the base $$$k$$$ numbers and finally converting it back to decimal. The time complexity for each of these operations will be $$$\mathcal{O}(\log_k n)$$$.
2. At any stage, the maximum number that we could be dealing with will be non-negative and will not exceed $$$n\times k$$$ as the $$$k$$$-itwise operations do not add extra k-its. This fits well within the limits of $$$y$$$ which is $$$2\cdot 10^7$$$.
Time Complexity - $$$\mathcal{O}(n\cdot \log_{k} n)$$$.