H. Hamming Guess
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

Aladdin has found the magical lamp and awakened the Genie inside it. He wished to become the richest man in the kingdom. The Genie agreed to grant Aladdin his wish and said he would do so by granting him $$$n$$$ golden coins. However, there was one condition for the wish to come true, Aladdin must guess the number. The Genie told Aladdin that he has at most $$$29$$$ tries to guess $$$n$$$, and that the number of golden coins is at least $$$1$$$ and at most $$$10^9$$$.

To find the secret number, Aladdin needs to make guesses, where in each guess he proposes a number. After each guess, the Genie will reveal to Aladdin the Hamming distance between the guess and $$$n$$$.

The Hamming distance between $$$2$$$ integers is the number of bits that are different at the same position in both numbers in their binary representation. For example, the Hamming distance between $$$9$$$ and $$$14$$$ is $$$3$$$.

Aladdin really wants to get rich. Can you help him uncover the number of golden coins before all his wishes are gone?

Interaction

To make a query, you have to print a line "$$$?$$$ $$$x$$$" $$$(0 \le x \le 10^{9})$$$

After each query, read a single integer $$$k$$$ $$$(0 \le k \le 30)$$$ – the Hamming distance between $$$n$$$ and $$$x$$$.

When you find $$$n$$$, print a line "$$$!$$$ $$$n$$$". Printing $$$n$$$ is not counted as one of 29 operations.

Example
Input

3

4

2

0
Output
? 24

? 55

? 8

? 4

! 4
Note

After printing a query or the answer, do not forget to output an 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;

- stdout.flush() in Python;