题目描述

这是一个交互题。

评测机会在区间 $[1,10^9]$ 中选择一个整数，你应该写一个代码来猜测它。你最多可以问评测机 $50$ 次。

对于每一次询问，你可以向评测机询问区间 $[1,10^9]$ 中的一个整数，评测机会返回:

• $0$，如果它为答案（即评测机所选的数字），且程序应该在此之后停止询问。
• $-1$，如果它小于答案。
• $1$，如果它大于答案。

每次询问，你需要按照如下格式向标准输出输出：

• $\texttt{? a}$ —— 表示你向评测机询问的一个整数。

你必须在 $50$ 次询问之内找到评测机选择的整数。

输入格式

无

交互格式

你必须在 $50$ 次询问之内找到评测机选择的整数。

• 要进行查询，请输出一行格式为 $\texttt{? a}$ 的数据，$(1\le a \le 10^9)$，每次查询后，读取一个整数，即查询的结果。
• 要报告答案，请输出一行格式为 $\texttt{! a}$ 的内容，其中 $a$ 表示你找到的评测机选择的整数。

在 $50$ 次查询之后，评测机的返回结果都是 $0$。你应该自行判断是否为正确答案。

打印完每一行后，不要忘记输出行尾并刷新输出缓冲区。你可以使用如下语句来清空缓冲区：

• 对于 C/C++：fflush(stdout)；
• 对于 C++：std::cout << std::flush；
• 对于 Java：System.out.flush()；
• 对于 Python：stdout.flush()；
• 对于 Pascal：flush(output)；
• 对于其他语言，请自行查阅对应语言的帮助文档。

特别的，对于 C++ 语言，在输出换行时如果你使用 std::endl 而不是 '\n'，也可以自动刷新缓冲区。建议使用std::endl以避免忘记输出换行。

输入输出样例

1

-1

0

? 5

? 10

? 7

! 7

样例解释

假设评测机选择的数字是 $7$。

我们第一次询问 $5$，评测机返回 $1$，说明我们选择的数字小了。

第二次询问 $10$，评测机返回 $-1$，说明我们选择的数字大了。

第三次询问 $7$，评测机返回 $0$，说明我们找到了！。

所以第四次直接输出 $\texttt{! 7}$ 表示我们的答案。