题目描述

Laur 老师为他的 $N$ 名学生组织了一场编程比赛，现在他想按照比赛成绩给学生发奖品。奖品原本已经按正确顺序摆在架子上，但 Toots 胡闹时把架子弄翻了。由于所有奖品都装在相同的盒子里，老师只能把它们随机放回架子上。

不同奖品的重量不同。老师有一架天平，可以比较两个盒子，从而判断哪一个盒子里的奖品应该发给成绩更好的学生。但是每次称重都需要时间，而已经有前 $M$ 名学生在门外排队等待领取奖品。

为了尽量减少所有学生等待奖品的总时间，老师希望用尽可能少的称重次数确定每名学生的奖品。请你编写程序帮助老师完成这件事。

交互格式

当你的程序开始运行时，输入的第一行包含两个整数 $N$ 和 $M$，分别表示奖品数量和已经排队等待的学生数量。

$$1 \le N \le 100,\quad 1 \le M \le N$$

奖品盒子按照它们在架子上的顺序编号为 $1,2,\ldots,N$。

随后，评测系统会向你的程序发送 $M$ 个询问。你的程序必须依次处理每个询问并回答；只有在你回答完当前询问后，评测系统才会给出下一个询问。

每个询问为一个整数 $K$，表示下一个进来领取奖品的学生在比赛中的名次为第 $K$ 名。比赛中没有并列名次。

对于当前询问，你的程序可以向老师请求若干次称重。若要请求一次称重，你的程序应输出一行：

? A B

其中 $A$ 和 $B$ 是两个不同的奖品盒编号，满足：

$$1 \le A \le N,\quad 1 \le B \le N,\quad A \ne B$$

评测系统会在下一行返回本次称重结果：

• <：表示盒子 $A$ 中的奖品应发给成绩更好的学生；
• >：表示盒子 $B$ 中的奖品应发给成绩更好的学生。

当你的程序确定第 $K$ 名学生对应的奖品在哪个盒子中后，应输出一行：

! C

其中 $C$ 是该奖品盒编号，满足 $1 \le C \le N$。输出这一行后，当前询问处理完成。如果还有后续询问，评测系统会继续给出下一个整数 $K$；如果已经回答完所有 $M$ 个询问，程序应正常结束。

评分方式

如果你的程序给任意一名学生发错了奖品，则该测试点得 $0$ 分。

如果所有奖品都发放正确，则按照学生总等待时间计算得分。具体地，若在仍有 $p$ 名学生等待时进行了一次称重，则这次称重产生 $p$ 点罚分。设整个测试点的罚分总和为 $P$，并令

$$Q=\frac{N\cdot M\cdot \log_2(N\cdot M)}{2}$$

则该测试点的得分比例为：

$$100\cdot \min\left(0.1+0.9^{100P/Q-99},\ 1\right)\%$$

你可以假设在所有测试点中，奖品顺序和学生到达顺序都是随机选择的。

交互示例说明

下面说明一个例子。有 $3$ 个奖品，$2$ 名学生正在等待。假设奖品盒中的真实顺序为 $3,1,2$，即：

• 第 $1$ 个盒子中是第 $3$ 名的奖品；
• 第 $2$ 个盒子中是第 $1$ 名的奖品；
• 第 $3$ 个盒子中是第 $2$ 名的奖品。

第一个进入的是第 $1$ 名学生。程序请求称重盒子 $1$ 和 $2$，系统返回盒子 $2$ 中的奖品更好；随后程序请求称重盒子 $2$ 和 $3$，系统再次返回盒子 $2$ 中的奖品更好。因此第 $1$ 名的奖品一定在盒子 $2$ 中，程序输出盒子 $2$ 作为答案。

接着进入的是第 $3$ 名学生。程序请求称重盒子 $1$ 和 $3$，系统返回盒子 $3$ 中的奖品更好，因此第 $3$ 名的奖品一定在盒子 $1$ 中，程序输出盒子 $1$ 作为答案。

所有询问处理完毕后，程序结束。此过程中产生的罚分为：

$$2\cdot 2+1\cdot 1=5$$

即在还有 $2$ 名学生等待时进行了 $2$ 次称重，在还有 $1$ 名学生等待时进行了 $1$ 次称重。该例中可获得 $100\%$ 的测试点分数。

输出刷新要求

由于这是交互题，你每输出一行后都必须刷新输出缓冲区，否则评测系统可能无法及时收到你的输出。

常见语言的刷新方式如下：

语言	建议写法
C	printf(...); fflush(stdout);
C++	cout << ... << endl;
Java	System.out.println(...); System.out.flush();
Python	print(..., flush=True) 或手动调用 sys.stdout.flush()

说明

本 Hydro 数据包中的测试数据内部格式包含奖品真实顺序和学生询问序列，这些内容由交互器读取。选手程序实际只能看到交互器按照上述协议发送的 $N,M$、每个询问 $K$ 和称重结果。