You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有 $T$ 组数据，每次给您两个正整数 $n,k$。

你需要猜一个正整数 $q$，保证 $q\in [1,n]$。

你每次可以用诸如 ? x 的询问，然后交互库会输出形如 d 的回答，$d=|q-x| \bmod k$，对于每组数据您可以至多进行 $100$ 次这样的查询。

你可以通过 ! x 输出你认为正确的 $q$。每组数据，您至多只能进行一次这样的操作，在进行之后，你应该刷新缓冲区并读入两个正整数 $n,k$，表示下一次的询问。（如果这是最后一组，则不需要此操作）

现在你要求出 $q$。

需要注意的是，在每一次操作后，需要调用以下函数刷新缓存：

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

每一次一开始交互库会给你 $n,k$，然后你可以按题目描述中的方式进行询问或回答答案。

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

输入格式

无

输出格式

无

输入输出样例 #1

输入 #1

1
3 5

2

输出 #1

? 1

! 3

说明/提示

本题采用捆绑测试计分。每组数据中只有全部通过 $T$ 次测试才可以获得全部分数。

对于所有数据，保证 $2 \le n\le 10^{12},3 \le k \le 10^{12},1 \le T \le 20$。