E2. Game of Scientists (Version 2)
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The two versions have different constraints on $$$k$$$, $$$c$$$. Solving one of the two versions does not necessarily solve the other. You may want to read both versions. Hacks are disabled in both versions.

This is an interactive problem.

During the time of the Ottoman Empire, many scientists were at work. You decided to study their daily life and stumbled upon an interesting game that was popular at that time. One scientist would think of an integer $$$x$$$, such that $$$1 \leq x \leq c$$$. Another scientist would try to guess it. He could specify the base of the numeral system $$$2 \leq b \leq c$$$ and would receive as a response the sum of the digits of the number $$$x$$$ in base $$$b$$$, if $$$x \geq b$$$, or $$$-1$$$ if $$$x \lt b$$$.

You wrote a program that can think of a number $$$x$$$ and respond to the question. Now you want to play with it and learn to guess using $$$\leq k$$$ queries.

Input

The first line contains three integers $$$t$$$, $$$k$$$, $$$c$$$ ($$$1 \leq t \leq 10^4$$$, $$$\mathbf{k=3}$$$, $$$\mathbf{c=2\cdot10^9}$$$). You must guess the number from $$$1$$$ to $$$c$$$ $$$t$$$ times, using $$$\leq k$$$ queries. All $$$t$$$ games will be played consecutively and are independent.

Interaction

To make a query, you must output ? $$$b$$$ for some $$$2 \leq b \leq c$$$. Then you must read the response — an integer $$$a$$$ ($$$-1 \leq a \lt c$$$) — the response to the query.

To provide the guessed number, you must output ! $$$x$$$, where $$$1 \leq x \leq c$$$ — your answer. Then you must read the result $$$r$$$ ($$$0 \leq r \leq 1$$$). If $$$r = 0$$$ — your answer is incorrect, you must immediately terminate the program in this case. Otherwise, if $$$r = 1$$$ — your answer is correct, you can proceed to the next game or terminate the program if $$$t$$$ games have already been played.

It is guaranteed that the interactor is not adaptive. That is, all chosen numbers are fixed in advance and do not change during the games.

After printing each query do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict.

If, at any interaction step, you read -2 instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

$$$^{\text{∗}}$$$To flush, use:

  • fflush(stdout) or cout.flush() in C++;
  • sys.stdout.flush() in Python;
  • see the documentation for other languages.
Example
Input
3 3 2000000000

1

1

7

1

-1

1

-1

6

6

1
Output

? 10

? 1000

? 2

! 1000000

? 2

! 1

? 100

? 10

? 5

! 42
Note

In the first game, the hidden number is $$$1000000_{10} = 100_{1000} = 11110100001001000000_2$$$. The sums of digits are $$$1$$$, $$$1$$$, and $$$7$$$ in these bases.

In the second game, the hidden number is $$$1$$$. The query with $$$b = 2$$$ returns $$$-1$$$.

In the third game, the hidden number is $$$42_{10} = 132_{5}$$$.