This is an interactive problem.

There is a cute little magician in a cyan outfit waiting for your command. There is a hidden integer $x$ ($1 \le x \le 10^9$). You want to find it by asking the magician whether a certain integer $y$ is greater than $x$.

You can use the format "? $y$" to make a query. When $y > x$, the magician will reply $1$; when $y \le x$, the magician will reply $0$.

Interaction

You can make at most $100$ queries. To make a query, print "? $y$" ($1 \le y \le 10^9$) on a single line, and then read the response from standard input.

To output your answer, print "! $x$" on a single line. The output of the answer does not count towards the $100$ query limit.

After that, your program should terminate.

After printing a query, do not forget to print a newline and flush the output. For example, use fflush(stdout) or cout.flush() in C++, System.out.flush() in Java, flush(output) in Pascal, or stdout.flush() in Python.

It is guaranteed that the number is fixed in advance.

Examples

Input 1

0
0
0
1

Output 1

? 1
? 2
? 3
? 4
! 3