题目描述

题目译自 NordicOI 2022 T3 「Quark Microscopy」

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

这些 $N$ 个夸克位于一条 $1$ 米（$10^{18}$ 阿米）长的线上。你有一个非常精确但有点古怪的夸克显微镜，它能够检测并测量附近夸克的距离。由于量子效应，它不能直接告诉你离测量位置最近的夸克的位置，而是告诉你第二近的距离！它还会告诉你在这个距离上的夸克数量。

具体来说：你可以在这条线上整数位置 $x$ 进行测量。对于每次测量，显微镜会确定从 $x$ 到所有夸克的距离 $d_1, d_2, \ldots, d_n$，并按升序排列，然后你会得到 $d_2$，以及满足 $d_i = d_2$ 的索引数量（要么是 $1$，要么是 $2$）。在进行足够多的测量后，你需要回答所有夸克的位置。

每个夸克的位置是从线的起点开始的 $1$ 到 $10^{18}$ 之间的整数。根据泡利不相容原理，没有两个夸克会占据相同的位置。

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

交互方式

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

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

• $\texttt{?}\,x$ ($-10^{18} \le x \le 2 \cdot 10^{18}$)：查找距离 $x$ 第二近的夸克的距离。评测系统会回应两个用空格分隔的数字 $r$ 和 $m$，其中 $r$ 是距离第二近的夸克的距离，$m$ 是在这个距离上的夸克数量（要么是 $1$，要么是 $2$）。
• $\texttt{!}\,a_1\,a_2\,\ldots\,a_n$ $(1 \le a_i \le 10^{18})$：猜测所有夸克的位置。$a_1, a_2, \ldots, a_n$ 可以按任意顺序给出。此后不应再进行其他查询。

每次查询后，你应确保刷新标准输出，然后再读取评测系统的响应，否则你的解决方案可能会被判定为超时。

如果你进行无效查询，你的程序可能被判为 Wrong Answer 或 Runtime Error。

为了方便测试你的解决方案，我们提供了一个简单的工具，你可以在「文件」中下载。请参阅文件顶部的注释，了解如何使用它。

样例 1

样例 2

数据范围与提示

详细子任务附加限制及分值如下表所示。

对于每个子任务，令 $Q$ 为该组中测试点中使用的 $\texttt{?}$ 型查询的最大数量。然后，该子任务的 $r$ 根据下表定义：