题目背景

为了方便调试，我们在附件中提供了交互库。

题目描述

这是一道交互题。在本题中，交互库在每一轮中是非自适应的。请关注本题中排列的特殊性。

存在一个长度为 $N$ 的隐藏排列 $P_1, P_2, \dots, P_N$，并保证其是均匀随机生成的。该排列以某种未知顺序恰好各包含一次数字 $1, 2, 3, \dots, N$。

你可以选择位置 $l$ 和 $r$，并提出如下形式的问题：「$P_l + P_{l+1} + \dots + P_r$ 的和是多少？」

你的任务是在尽可能少的提问次数内，找出 $P$ 中数字 $1$ 所在的位置。你的得分取决于你提问的次数。

实现细节

你的程序首先应在一行中读入两个整数 $T$ 和 $N$。$T$ 是程序将运行的轮数，$N$ 是 $P$ 的长度。

接下来进行 $T$ 轮：

当一轮开始时，你可以开始提问。输出一行 $\texttt{? a b}$ 来询问位置 $a$ 到 $b$ 之间数值的和（$1 \le a \le b \le N$）。

每次提问之后，你的程序应读入一个整数，即该区间内数值的和。

当你找到了数字 $1$ 所在的位置后，输出一行 $\texttt{! i}$，其中 $i$ 是满足 $P_i = 1$ 的下标。输出后开始下一轮（或终止程序）。

请确保在每次询问后刷新输出，否则可能会被判为 Time Limit Exceeded。在 C++ 中可以使用例如 cout << flush 或 fflush(stdout)；在 Python 中使用 stdout.flush()；在 Java 中使用 System.out.flush()。

输入格式

见「实现细节」。

输出格式

见「实现细节」。

2 10

55

40

1


1

? 1 10

? 1 5

? 6 6

! 6
? 1 1

! 1

提示

计分方式

你的程序将在唯一的一个测试点上进行测试，该测试点满足 $N = T = 1000$。

如果任意一轮给出了错误答案，提交将被判为 Wrong Answer。

令 $M$ 为你的程序在所有 $\boldsymbol{T}$ 轮中提出的问题总数。你的得分为 $\min(100, 220 - \frac{M}{2500})$ 分。如果得到负分，则记为 $0$ 分。

也就是说，如果你使用了超过 $550,000$ 次询问，你将得到 $0$ 分；如果使用了不超过 $300,000$ 次询问，你将得到 $100$ 分。介于两者之间时，得分按线性方式变化。