Description

At some moment, a golden tulip appears at some position. Then, starting from the next second, every second, each golden tulip will chant to all white tulips among the four adjacent points (up, down, left, right), turning them into golden tulips.

Now you are given a point $(x_0,y_0)$, and the second $t$ at which it has just turned into a golden tulip since the first golden tulip appeared. You need to find the position where the very first golden tulip appeared.

Each time, you may output one line 0 x y, then the program will return a value $0$ or $1$. $0$ means that $(x,y)$ is a white tulip at the $t$-th second, and $1$ means that $(x,y)$ is a golden tulip at the $t$-th second.
You may output one line 1 x y to tell the program that the position of the first golden tulip is $(x,y)$, and thus terminate the program.

Input Format

This problem has multiple test cases.
The first line contains a positive integer $Q$, meaning there are $Q$ test cases.
For each test case, the interaction starts by reading four integers $t,x_0,y_0,k$, separated by single spaces. They mean that at the $t$-th second, the tulip at $(x_0,y_0)$ has just turned golden. You can ask at most $k$ queries.

Output Format

For each test case, after you determine the answer, output one line 1 x y to end this test case, meaning you believe $(x,y)$ is where the golden tulip first appeared.

Interactive Format

During the interaction, output one line in the form 0 x y to perform one operation. Then you should read a boolean value, i.e., the return value $x$ of this operation. If $x=0$, it means $(x,y)$ is a white tulip at the $t$-th second; if $x=1$, it means $(x,y)$ is a golden tulip at the $t$-th second.

All inputs above should be read from standard input, and all outputs should be written to standard output. After outputting one line, you must flush the buffer, otherwise you may be judged as Time Limit Exceeded. Flush the buffer as follows:

• In C++, use fflush(stdout) or cout.flush().
• In Pascal, use flush(output).
• For other languages, please check the documentation yourself.

2
1 1 0 100

0

0

1

2 1 1 10000

1

1

1

1

0 1 1

0 1 -1

0 0 1

1 0 0

0 2 0

0 0 2

0 -2 0

0 0 -2

1 0 0

Hint

Each test point is worth $5$ points.

Note: In the worst case, asking $MAX=\lceil\log_2(t+1)\rceil+2$ times is guaranteed to obtain the answer. It is guaranteed that $1 \le t \le 10^4$, $1 \le Q \le 5000$, and the absolute values of the resulting $x,y$ are not greater than $10^5$.

Hint: Due to the nature of interactive problems, if your algorithm is wrong, it is normal for the judge result to be TLE. Please move the mouse over the test point to see the specific error reason. Specifically:

• If your output answer is wrong, it will return You made a mistake in data i!.
• If you ask too many queries, it will return You ask too many times in data i!.

Translated by ChatGPT 5