J. Guess the Number!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Magikarp loves to read minds! Now, he will challenge you to read his mind.

Magikarp has chosen a number $$$x$$$ $$$(1\le x\le 10^6)$$$. You can ask him questions of the form "Is $$$x$$$ at least $$$k$$$?". He will answer 1 if the answer is "Yes", and 0 if the answer is "No".

Magikarp realizes this is quite easy if you can ask as many questions as you want, so he will try to challenge you! Solve this when the number of questions you can ask is at most $$$4!$$$

Input

This is an interactive problem, so there is no input to read at the start.

Output

To ask a question, print a line of the form ? k where $$$1 \le k \le 10^6$$$.

After printing a question, you must flush the output and then read one integer from the interactor:

  • 1, if $$$x \ge k$$$
  • 0, if $$$x \lt k$$$

When you are ready to give your final answer, print a line of the form ! y where $$$y$$$ is your guess for $$$x$$$.

After printing your final answer, flush the output and terminate immediately.

Interaction

The hidden integer $$$x$$$ is fixed for the entire test.

If your program asks more than the allowed number of queries, prints an invalid query, uses a value of $$$k$$$ outside the allowed range, or does not follow the required format, the verdict may be Wrong Answer.

Remember to flush the output after every query and after the final answer. For example:

  • in C++, use cout « endl; or cout.flush();
  • in Java, use System.out.flush();
  • in Python, use sys.stdout.flush()
Example
Input
5
Output