Problem Description

This is an interactive problem.

Maddy and Buddy are playing a guessing game with a hidden mechanism.
Maddy has now hidden a mechanism on the 2D coordinate plane. The mechanism must be one of the following two types:

• Bumper: a lattice circle with center at $(0, 0)$. There is at least one positive lattice point on the circle (i.e., at least one point whose $x$ and $y$ are both positive integers), and the absolute values of its coordinates are less than $10^5$.
• Kevin: a lattice square with center at $(0, 0)$. Each vertex lies on a lattice point (i.e., both coordinates are integers), and the absolute values of its coordinates are less than $10^5$. The square is guaranteed to be non-degenerate, i.e., its side length is at least 1.

But Buddy does not know what the mechanism is. Each time, she can ask Maddy a question:

• Is the lattice point $(x, y)$ outside the shape represented by the mechanism (the boundary is considered inside the shape)?
• Maddy will tell her whether the point is outside or inside the shape. If the point lies on the boundary, Maddy will tell Buddy that the point is inside.

Buddy can ask at most 35 questions. She needs to tell Maddy:

• Whether the mechanism is Kevin, Bumper, or whether there are two possible answers.

Note that outputting your final answer does not count toward the 35 queries.

Interaction Format

The first line contains an integer $T$ ($1 \le T \le 10^3$), the number of testdata.
For each test case, the interactive process starts immediately. Each time you may query the interactor in the following format:

• Output one line. First output a character ? indicating a query, then output two integers $x$ and $y$ indicating that you want to ask whether the point $(x, y)$ is outside the mechanism. You must ensure $0 \le |x|, |y| \le 2 \times 10^5$.
• If your query is valid and you have not exceeded the query limit, the interactor will output one line containing a string $Q$. If $Q = \text{IN}$, then $(x, y)$ is inside the shape represented by the mechanism or on its boundary; if $Q = \text{OUT}$, then $(x, y)$ is outside the shape represented by the mechanism.
• If you exceed the query limit, the interactor will output an integer $-1$ and terminate your interaction process immediately. You will receive a Wrong Answer verdict.

If you have determined the answer, output it in the following format:

• Output one line, first output a character !.
• Then output a string $S$. $S$ must be Bumper, Kevin, or NotConfirm, meaning the mechanism is a Bumper, the mechanism is Kevin, or there are two possible answers, respectively.

If your answer is correct, the interactor will output one line containing the string Correct!. Otherwise, it will output one line containing an integer $-2$ and terminate immediately. You will receive a Wrong Answer verdict.
After finishing one test case, you should immediately start querying for the next test case. If it is the last test case, you may exit safely.
The interactor is not adaptive. This means the mechanism is fixed before each test case starts and will not change during the interaction.
After each output, you must print a newline and flush the buffer, otherwise you may get unexpected results.
If you receive interactor error messages $-1$ or $-2$, terminate your interaction process as soon as possible, otherwise you may get unexpected results (e.g., TLE).
To flush the buffer, you may use:

• For C or C++, use fflush(stdout) or cout.flush().
• For Java or Kotlin, use System.out.flush().
• For Python, use stdout.flush().

Output Format

Hint

1
IN
IN
OUT
IN
Correct!

? 1 0
? 0 1
? 100 100
? 0 2
! Bumper

Hint

Hint

Please note that the interactive process in the sample is for reference only. The actual interactive process is not unique, and this example process may not be feasible or optimal. The samples for this problem will not appear in the additional files.
There are two possible answers if and only if:

• There exists a Kevin shape $K$ whose covered lattice-point set is $S_K$, and a Bumper shape $B$ whose covered lattice-point set is $S_B$, such that they are exactly the same as the lattice-point set $S_{\text{hidden}}$ covered by the currently hidden mechanism.

In this case, you cannot distinguish the two shapes by querying, so you should output NotConfirm.
However, if no such pair of mechanisms exists with identical covered sets, then you should be able to uniquely determine the mechanism type through your queries. In that case, outputting NotConfirm will be judged as Wrong Answer.

Translated by ChatGPT 5