猜数字

题目描述

这是一道交互题.

Orange最近迷上了猜数字这个游戏，简单来说，Orange会有一个数字 $a$，并把它记载心里，你每次可以向Orange提出询问，每次询问一个数字，Orange会告诉你这个数字与他心中所想的数字的大小关系，你需要依次作为判断，猜出Orange心里想的数字。

Orange保证，他心中所想的数字不会变化，且回答一定真实。请你在不超过30次询问内给出答案。

交互形式

本题的交互支持以下两种形式：

• $?$ $x$ - 表示向Orange提出你猜测的数，你将会得到一个整数 $p$，表示Orange对当前猜测的回答。其中 $p$ 满足:

$$p = \left\{ \begin{aligned} \ 1(x \ge a). \\ \ 2(x < a). \end{aligned} \right.$$

• $!$ $x$ - 表示向Orange报告你的答案。

交互说明

1. 每个测试用例都没有初始输入。交互开始时，您应提出一个问题。
2. 本题的交互是实时的，答案为随机生成。
3. 要进行查询，请输出一行格式为 ? x 的内容。我们会向您的程序输入一个整数，表示本次查询的结果。
4. 当你确定好你的答案时，请使用输出一行格式为 ! x 的内容，表示向Orange提交你的答案。提交答案不算作查询次数的一部分。
5. 如果你的程序长时间没有应答（可能是你关闭了cin以及cout的同步流），或者询问了非法的数据或者提交了错误的答案以及询问次数超过30次，程序均会返回答案错误。
6. 输出查询后，不要忘记输出行尾并刷新输出。否则，您可能会收到超过闲置限制的判定。为此，请使用：

• C++ 中使用 fflush(stdout) 或 cout.flush()；
• Java 中的 System.out.flush()；
• Pascal 中的 flush(output)；
• Python 中的 stdout.flush()；
• $\cdots$

特别提醒! 在回答交互性问题的时候，请不用关闭cin以及cout的同步流，避免交互程序无法收到您的交互请求。同时，如果你使用endl作为刷新缓冲区语句，请不用使用`#define endl \n。

输入格式

交互程序会根据您的交互请求进行响应。

输出格式

请输出您的交互请求。

样例 #1

样例输入 #1

1

1

1

1

2

样例输出 #1

? 100

? 50

? 25

? 10

? 5

! 10

提示

数据范围:

$1\le a \le 10^9$