Description

This is an interactive I/O problem.

This game is played in a 2D Cartesian coordinate system, on the origin, the positive $x$-axis and $y$-axis, and the first quadrant.

The interactor plays Black, and you play White. Black moves first, and it is guaranteed that the interactor’s first move is $(0,0)$. Both Black and White may only place pieces on points where both $x$ and $y$ are natural numbers.

If there appears a consecutive pattern Black White White White in any of the horizontal, vertical, or diagonal directions, then White wins. If you win in $x$ moves and $x\le 13$, then you get a score ratio of $\frac{\min(14-x,10)}{10}$.

Interaction Protocol

First, read an integer $T$, meaning $T$ games will be played.

For each of the next $T$ games, do the following:

You do not need to output the interactor’s first move $(0,0)$.

Then repeat the following two steps until you have made $14$ White moves or you win:

1. Output one line with two numbers x y, meaning you place a piece at $(x,y)$.

2. Read one line with two numbers x y, meaning the interactor places a piece at $(x,y)$. If you have already won after finishing the previous step, then you will not read these two numbers, and you should directly proceed to the next game.

In particular, to make interaction easier, all coordinates of your moves must be within $100$, otherwise you will be directly judged as having used $14$ moves and this game will end immediately. The interactor’s coordinates are also guaranteed to be within $100$. Also, if you place on an existing piece, it is considered that you placed this move to a very far place, i.e., you give up this move. If you want to give up actively, you may also use this method. Note that the interactor may also choose to give up some move.

Your final score ratio is the minimum score ratio among the $T$ games.

Input Format

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

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

Output Format

As described in the statement. After the interaction of the $T$ games ends, there should be no extra output.

1

0 0

0 0

0 1

0 2

0 3

Hint

[Sample Explanation]

Black always chooses to give up. White places $(0,1),(0,2),(0,3)$, which together with Black’s $(0,0)$ forms Black White White White in the vertical direction. Therefore, White wins.

This problem uses bundled testdata.

• Subtask 1 (10 pts): The interactor is guaranteed to place randomly at some point.
• Subtask 2 (10 pts): The interactor is guaranteed to always give up, except when you can win for sure in your next move.
• Subtask 3 (20 pts): $T=5$.
• Subtask 4 (60 pts): No special restrictions.

For $100\%$ of the testdata, $1\le T\le 10^3$.

Translated by ChatGPT 5