Description

这是一道 IO 交互题。

可不有 $n$ 朵花，每朵花有一个正整数美丽度。

她发现，有一朵花的美丽度不小于其它任何一朵花的美丽度的两倍。

你想知道这朵花是哪一朵，于是你可以进行至多 $k$ 次询问，每次询问你给出两个正整数 $i,j \in [1, n]$，可不会告诉你第 $i$ 朵和第 $j$ 朵花的美丽度之差的绝对值。

你想运用这些询问的答案，得到最美丽的花是第几朵。

交互格式

本题有多组数据。

第一行交互库给出一个整数 $T$，表示数据组数。

对于每组数据，第一行输入两个正整数 $n,k$。

对于你的每组询问，你输出 ? i j，交互库会返回一个非负整数，表示第 $i$ 朵和第 $j$ 朵花的美丽度之差。

如果你已经得到答案，输出 ! i 代表你得到第 $i$ 朵花为最美丽的花。在此之后你应该开始对下一组数据的处理。

每次你输出之后，请刷新缓冲区。

你可以使用如下语句来清空缓冲区：

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

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

Input Format

见「交互格式」。

Output Format

见「交互格式」。

1
3 114514

3

2

1

? 1 2

? 1 3

? 2 3

! 1

Hint

样例中给出了一种可能的交互方式，其中花的美丽度为 $\{4,1,2\}$。

本题采用捆绑测试。

• Subtask 1（20 points）：$k=\dfrac{n(n-1)}{2}$，$n \le 200$。
• Subtask 2（30 points）：$k=n$。
• Subtask 3（50 points）：$k=\left\lfloor\dfrac{n}{2}\right\rfloor+2$。

对于所有测试数据，设所有花的美丽度为 $a_i$，$1 \le T \le 25$，$3 \le n \le 5 \times 10^4$，$1 \le a_i \le 10^8$。