灾难降临了！Niels 珍贵的宠物原子被宇宙射线击中，分裂成了一堆独立的夸克。Niels 现在急于找到这些夸克并将它们重新拼凑起来，他向你寻求帮助。

这 $N$ 个夸克位于一条 1 米（$10^{18}$ 阿托米）长的直线上。你拥有一台非常精密（但有些古怪）的夸克显微镜，它能够探测并测量到附近夸克的距离。由于量子效应，它无法直接告诉你距离测量位置最近的夸克在哪里。相反，它会告诉你到第二近的夸克的距离！它还会确定在该距离上有多少个夸克。

更准确地说：你可以在直线上的整数位置 $x$ 进行测量。对于每次测量，系统会确定从 $x$ 到所有夸克的距离 $d_1, d_2, \dots, d_n$，并将它们按升序排列。你将获得 $d_2$，以及满足 $d_i = d_2$ 的索引 $i$ 的数量（该数量为 1 或 2）。在执行足够的测量后，你应该回答所有夸克的位置。

每个夸克在直线上都有一个介于 1 到 $10^{18}$ 阿托米之间的整数位置（从直线起点开始计数）。没有两个夸克会占据相同的位置（根据泡利不相容原理）。

根据执行的测量次数，你的程序将获得不同数量的分数。

交互

你的程序将通过从标准输入读取和向标准输出写入来与评测机进行交互。首先，评测机将输出一行，包含夸克的数量 $N$ ($3 \le N \le 100$) 和测试组编号 $T$ ($1 \le T \le 3$)。

然后，你的程序可以进行以下形式的查询：

• ? x ($-10^{18} \le x \le 2 \cdot 10^{18}$): 查询到距离 $x$ 第二近的夸克的距离。评测机将返回两个空格分隔的数字 $r, m$，其中 $r$ 是到第二近夸克的距离，$m$ 是在该距离上的夸克数量（为 1 或 2）。
• ! a1 a2 . . . an: 猜测夸克的位置 ($1 \le a_i \le 10^{18}$)。$a_1, a_2, \dots, a_n$ 可以以任何顺序给出。此后不得进行任何额外查询。

每次查询后，请确保在读取评测机的响应之前刷新标准输出，否则你的程序可能会被判为超时（Time Limit Exceeded）。在 Python 中，这会自动完成；在 C++ 中，使用 cout << endl; 打印换行符即可。在 C 语言中，可以在 printf 后使用 fflush(stdout);。

如果你进行了无效的查询，你的程序可能会收到“答案错误”（Wrong Answer）或“运行时错误”（Run Time Error）。

为了方便测试你的程序，我们提供了一个简单的工具，你可以在本页面顶部下载。请参阅文件顶部的注释以获取使用说明。

子任务

你的程序将在多组测试数据上进行测试，每组测试数据都有一定的分值。要获得某测试组的分数，你需要解决该测试组中的所有测试用例。

对于每个测试组，令 $Q$ 为该组中所有测试用例所使用的 ? 类型查询的最大次数。那么该组的 $r$ 根据下表定义：

样例

样例 1

3 3
? 5
6 1
? 15
4 1
? 11
1 2
! 11 10 12

样例 2

3 1
? 1
2 1
? 2
1 2
? 3
2 1
? 47
45 1
! 1 3 92