题目背景

这是一道交互题！

特别提醒：本题为 0-indexed。

为了适配洛谷评测机，本题改用 IO 交互。

题目描述

在第 $8$ 届 eJOI 举行之际，$N$ 位选手正围成一圈跳霍拉舞！这里，$N$ 是一个正偶数，且这 $N$ 名选手中男女人数相同。组织者为每名选手分配了一个编号，从 $0$ 到 $N-1$。编号是顺着分配的，也就是说，$i$ 与 $i-1$ 和 $i+1$ 相邻；特别的，$0$ 与 $1$ 和 $N-1$ 相邻。

你并不知道哪些选手是男生，哪些选手是女生。但是，由于你正在比赛中，所以你只能向评测机问问题！在一次问题中，你可以给两个整数 $L$ 和 $R$，保证 $0 \le L,R < N$，然后：

• 如果 $L\le R$，评测机会返回 $[L,R]$ 中男生的数量。

• 否则，评测机会返回 $[L,N-1]$ 和 $[0,R]$ 中总共男生的数量。

给你一个 $K$，现在，你需要通过询问评测机若干个如上问题，来找到这个环中长度为 $K$ 的一段，使得这一段中男生和女生人数差最小。你需要输出在圆上连续的这一段的起点 $S$。如果有多个这样的 $S$，你可以输出任意一个。

输入格式

输入一行两个整数 $N,K$。

输出格式

如果你认为你找到了正确答案 $x$，输出 ! x 结束交互。

交互过程

你需要输出 ? L R 来进行询问，评测机会将结果返回到输入中，然后你进行读取。

上述的所有输入都应从标准输入中读入，所有输出都应向标准输出中输出。输出一行后必须清空缓冲区，否则你的评测将被判为 Time Limit Exceeded。清空缓冲区方式如下：

• 在 C++ 中，使用 fflush(stdout) 或 cout.flush()。
• 在 Pascal 中，使用 flush(output)。
• 在 Python 中，使用 stdout.flush()。
• 其他语言请自行查阅文档。

如果你的输出格式错误，或执行超过 $100000$ 次操作，你的评测将被判为 Wrong Answer。

12 5

6

4

3

? 0 10

? 0 4

? 1 5

! 1

提示

【样例解释】

排列如下：

其中一种正确答案是 $1$，因为 $[1,5]$ 中有 $3$ 男 $2$ 女，差为 $3-2=1$，为最小。

【数据范围】

对于 $100\%$ 的数据，$2 \le N \le 10^5$，$N$ 为偶数，$1 \le K \le N$，交互库不自适应（即，男女生的分布在一开始就已经确定，不会改变）。

$\text{Subtask}$	分值	特殊性质	$Q_{full}$
$1$	$5$	$N=34$	$34$
$2$	$13$	$N=100000$，所有男孩都相邻	$18$
$3$	$8$	$N=100000$，数据随机	$34$
$4$	$11$	$N=100000,K=50000$	$18$
$5$	$10$	$N=65536,K=128$	$26$
$6$		$N=100000,K=400$
$7$	$9$	$N=100000,K=99601$
$8$	$10$	$N=100000,K=330$	$68$
$9$	$24$	无	$34$

【计分方式】

在每一个 $\text{Subtask}$ 中都有 $Q_{full}$ 和分值。假设在你一共询问了 $Q$ 次。

• 如果 $Q\le Q_{full}$ 你就可以得到该测试点的全部分数。

• 如果 $N\ge Q\ge Q_{full}$ 那么你可以得到分值 $\times\Bigg(1-\Bigg(\dfrac{(Q-Q_{full})}{N}\Bigg)^{0.05}\Bigg)$ 分。

• 如果 $Q>N$ 那么你不得分。

一个 $\text{Subtask}$ 的得分是其所有测试点的得分最小值。