这是一个交互式问题。

有一个隐藏的整数 $x$，满足 $1 \le x \le 10^9$。

你需要通过询问某个整数 $y$ 是否大于 $x$ 来找到它。

你可以使用格式 “? $y$” 进行询问，交互器会在 $y > x$ 时返回 1，在 $y \le x$ 时返回 0。

交互

你最多可以进行 100 次询问。进行询问时，请在单独的一行输出 “? $y$” ($1 \le y \le 10^9$)，然后从标准输入读取响应。

给出答案时，请在单独的一行输出 “! $x$”。输出答案不计入 100 次询问的限制。

在此之后，你的程序应该终止。

在打印询问后，请务必输出换行并刷新缓冲区。为此，在 C++ 中使用 fflush(stdout) 或 cout.flush()，在 Java 中使用 System.out.flush()，在 Pascal 中使用 flush(output)，或者在 Python 中使用 stdout.flush()。

样例

输入 1

0
0
0
1

输出 1

? 1
? 2
? 3
? 4
! 3