K. Sin
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This in an interactive problem.

Note: This problem uses an adaptive interactor.

This problem was written on May 20th.

In this school contest, I committed three crimes.

The crime of adding $$$0$$$ to the data range, causing a division by zero error if the code does not handle it as a special case.

The crime of setting the upper bound of binary search to $$$10^{18} + 10^9$$$, and making intermediate variables reach the order of $$$10^{23}$$$, leading to an extremely error-prone upper bound and integer overflow in the code.

And... and there's more...

The felony of replacing the problem four days before the contest, creating a new problem, and intentionally writing a wrong interactor...

To test the support for interactors on the school contest platform, xyz tried to implement an adaptive interactor for the classic interactive template (binary number guessing). Unfortunately, he wrote the interactor incorrectly.

The description of the number guessing problem is as follows: The judge has a positive integer $$$x$$$ in the range $$$[1, 10^9]$$$. You need to guess the value of $$$x$$$ with no more than $$$100$$$ queries. For each query, you ask the judge for a positive integer $$$y$$$ in $$$[1, 10^9]$$$. The judge returns $$$1$$$ if $$$y \ge x$$$, and returns $$$0$$$ if $$$y \lt x$$$.

The logic of the wrong interactor designed by xyz is as follows: To maximize the number of subsequent queries required by the guessing program, the interactor should choose the response that results in a longer new interval. If the lengths are equal, either choice is acceptable (usually $$$0$$$ or $$$1$$$). In this way, after each response, the interval size is at least half of the original interval size (rounded up), making the number of queries approach the information-theoretic lower bound $$$\lceil \log_2 10^9 \rceil = 30$$$.

xyz believed that if the existing conditions only imply that $$$x$$$ lies in the interval $$$[l, r]$$$, the correct choice can be made by comparing $$$|y - l|$$$ and $$$|y - r|$$$. Thus, he implemented the following rules:

  • If $$$|y - l| \gt |y - r|$$$, the interactor returns $$$1$$$;
  • If $$$|y - l| \lt |y - r|$$$, the interactor returns $$$0$$$;
  • If $$$|y - l| = |y - r|$$$, the interactor returns $$$0$$$ with a $$$50\%$$$ probability and $$$1$$$ with a $$$50\%$$$ probability.

The way to determine $$$l$$$ and $$$r$$$ in xyz's wrong interactor is as follows:

  • If no query response is $$$1$$$ so far, then $$$r = 10^9$$$;
  • Otherwise, let the values of queries with response $$$1$$$ be $$$a_1, a_2, \cdots, a_n$$$, then $$$r = \min_{i = 1}^n a_i$$$;
  • If no query response is $$$0$$$ so far, then $$$l = 1$$$;
  • Otherwise, let the values of queries with response $$$0$$$ be $$$b_1, b_2, \cdots, b_m$$$, then $$$l = \max_{i = 1}^m b_i + 1$$$.

According to the definition of the response, the true value $$$x$$$ must lie within the interval $$$[l, r]$$$, and this is the minimal possible interval derived from the existing responses.

For example, if it is currently only known that $$$x$$$ is in the interval $$$[5, 9]$$$ (i.e., $$$l=5, r=9$$$), when querying $$$y = 7$$$, xyz's wrong interactor compares $$$|7-5|=2$$$ and $$$|7-9|=2$$$. Since they are equal, it returns $$$1$$$ with a $$$50\%$$$ probability and $$$0$$$ with a $$$50\%$$$ probability. If it returns $$$1$$$, the new interval becomes $$$[5, 7]$$$; if it returns $$$0$$$, the new interval becomes $$$[8, 9]$$$. This wrong interactor has a $$$50\%$$$ chance to choose the longer interval, which affects subsequent interval updates.

Note: Since xyz's interactor is implemented incorrectly, $$$l \le r$$$ is NOT guaranteed during the interaction. The response is only determined by the relative values of $$$|y - l|$$$ and $$$|y - r|$$$.

Now, there are two types of interactors. The first is the correct interactor, which gives logically consistent results in all cases (it is an adaptive interactor, but its adaptation method may differ from any of those described in the problem statement). The second is xyz's wrong interactor, which interacts following the rules above. You can make no more than $$$100$$$ queries to the interactor to determine which type you are interacting with.

Note: The correct implementation of the adaptive interactor required to solve this problem is as follows:

  • If $$$|y - l + 1| \gt |y - r|$$$, the interactor returns $$$1$$$;
  • If $$$|y - l + 1| \lt |y - r|$$$, the interactor returns $$$0$$$;
  • If $$$|y - l + 1| = |y - r|$$$, the interactor returns $$$0$$$ with a $$$50\%$$$ probability and $$$1$$$ with a $$$50\%$$$ probability.
where $$$l$$$ and $$$r$$$ are generated in the same way as the rules above.

Note: The interactor in this problem will not adapt its type. For each test case, the type of interactor is pre-determined before any queries are made.

Interaction

This problem contains multiple test cases. The first line contains a positive integer $$$T$$$ $$$(1 \le T \le 100)$$$, denoting the number of test cases.

For each test case, repeat the following steps:

  1. You may output a query in the format ? $$$y$$$, where $$$y$$$ is an integer satisfying $$$1\le y\le 10^9$$$. The interactor will return an integer $$$0$$$ or $$$1$$$ on a separate line. See the problem statement for the exact meaning of the response.
  2. When you can determine the conclusion, output ! correct or ! wrong, indicating that you think the interactor is of the correct type or the wrong type, respectively. After this output, if there are subsequent test cases, the process will automatically move to the next one; if it is the last test case, the program should exit normally.
  • The number of queries per test case must not exceed $$$100$$$. If exceeded, the interactor will return Wrong Answer and terminate the program immediately.
  • You must output exactly one conclusion (! correct or ! wrong) for each test case, otherwise it will be judged as incorrect.

You must flush the standard output buffer after every output operation, otherwise the interactor may not receive your output in time, resulting in a time limit exceeded or wrong answer.

Methods to flush the output in common programming languages are as follows:

  • C++: std::cout.flush();
  • C: fflush(stdout);
  • Python: sys.stdout.flush() (requires import sys)
  • Other languages: Please refer to the corresponding documentation for methods to flush the standard output.
Example
Input
2

1


0

0

0
Output

? 400000000

! correct
? 1000

? 10000

? 100000

! wrong
Note

There are two test cases in the sample.

For the first test case, the pre-determined $$$x \le 4 \times 10^8$$$. Querying $$$4 \times 10^8$$$ returns $$$1$$$, which is impossible for the wrong interactor, so we can directly judge that the interactor is correct.

For the second test case, the interactor is wrong, and the returned results match the pattern of the wrong interactor. Even if you guess without certainty, the answer will be accepted as long as the guess is correct.