Bit Guessing Game

This is an interactive problem.

Kira has a hidden positive integer $$$n$$$, and Hayato needs to guess it.

Initially, Kira gives Hayato the value $$$\mathrm{cnt}$$$ — the number of unit bits in the binary notation of $$$n$$$. To guess $$$n$$$, Hayato can only do operations of one kind: choose an integer $$$x$$$ and subtract it from $$$n$$$. Note that after each operation, the number $$$n$$$ changes. Kira doesn't like bad requests, so if Hayato tries to subtract a number $$$x$$$ greater than $$$n$$$, he will lose to Kira. After each operation, Kira gives Hayato the updated value $$$\mathrm{cnt}$$$ — the number of unit bits in the binary notation of the updated value of $$$n$$$.

Kira doesn't have much patience, so Hayato must guess the original value of $$$n$$$ after no more than $$$30$$$ operations.

Since Hayato is in elementary school, he asks for your help. Write a program that guesses the number $$$n$$$. Kira is an honest person, so he chooses the initial number $$$n$$$ before all operations and does not change it afterward.

To guess $$$n$$$, you can perform the operation at most $$$30$$$ times. To do that, print a line with the following format: "- x" ($$$1 \le x \le 10^9$$$).

After this operation, the number $$$x$$$ is subtracted from $$$n$$$, and therefore $$$n$$$ is changed. If the number $$$x$$$ is greater than the current value of $$$n$$$, then the request is considered invalid.

After the operation read a line containing a single non-negative integer $$$\mathrm{cnt}$$$ — the number of unit bits in the binary notation of the current $$$n$$$ after the operation.

When you know the initial value of $$$n$$$, print one line in the following format: "! n" ($$$1 \le n \le 10^9$$$).

After that, move on to the next test case, or terminate the program if there are none.

If your program performs more than $$$30$$$ operations for one test case, subtracts a number $$$x$$$ greater than $$$n$$$, or makes an incorrect request, then response to the request will be -1, after receiving such response, your program must exit immediately to receive the Wrong Answer verdict. Otherwise, you can get any other verdict.

After printing a query or the answer, do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

Hacks

To make a hack, use the following format.

The first line should contain a single integer $$$t$$$ ($$$1 \leq t \leq 500$$$).

Each test case should contain one integer $$$n$$$ ($$$1 \leq n \leq 10^9$$$) on a separate line.