P10645 [NordicOI 2022] 夸克显微镜 Quark Microscopy

译自 Nordic Olympiad in Informatics 2022 [Quark Microscopy](https://noi22.kattis.com/contests/noi22/problems/quarkmicroscopy)。如果发现交互库锅了请联系搬题人 qvq。 $\texttt{1s,1G}$。

这下可惨了！Niels 珍爱的原子被宇宙射线击中，分裂成了许多夸克。Niels 迫切地想要找到这些夸克，然后将它们拼起来。所以，他找来了你来帮忙。 这 $N$ 个夸克分布在一条 $1$ 米（$10^{18}$ 阿米）长的线段上。幸运的是，你有一个很精确，但有点奇怪的夸克显微镜，它能够检测并测量邻近的夸克。然而由于量子效应，它无法直接告诉你离测量位置最近的夸克的位置，而是会告诉你离测量位置第二近的夸克的位置，以及离测量位置第二近的夸克的数量。 更为准确地说，你可以在线段上的位置 $x$ 处进行测量。对于每次测量，每个夸克距 $x$ 的距离将会被测出并升序排序，记为 $d_1,d_2,\cdots,d_N$。你会得到 $d_2$，和满足 $d_i=d_2$ 的 $i$ 的数量（只会是 $1$ 或 $2$）。在进行足够多次测量后，你需要回答每个夸克所在的位置。 每个夸克的位置都是介于 $[1,10^{18}]$ 间的正整数（单位：阿米），从线段的起始位置开始计算。由于 Pauli 不相容原理，夸克的位置不会重合。

你的程序与交互库通过标准输入输出流交互。 第一行，两个正整数 $N,T$，表示夸克的数量和子任务编号。 接下来，你的程序开始与交互库交互： - `? x`：询问离 $x$ 第二远的夸克。交互库会返回两个整数 $r,m$，其中 $r$ 是第二远夸克的距离，$m$ 是距离 $x$ 为 $r$ 的夸克的数量（只会是 $1$ 或 $2$）。你需要保证 $-10^{18}\le x\le 2\times 10^{18}$。 - `!` $a_1$ $a_2$ $\cdots$ $a_N$：回答夸克的位置。你可以以任意顺序给出这些夸克的位置。回答后，不应有多余的询问。你需要保证 $1\le a_i\le 10^{18}$。 **注意：在交互过程中，你需要在输出后刷新缓存区。** 下面是一些常见语言的刷新缓存区方式： - C++：`fflush(stdout)` 或 `cout.flush()`。特别地，利用 `std::endl` 换行也会刷新缓冲区。 - C：`fflush(stdout)`。

见【输出格式】。

#### 数据范围 - $3\le N\le 100$； - $1\le T\le 3$。 #### 评分方式 | 子任务编号 | 得分 | 限制 | | :--: | :--: | :--: | | $1$ | $40\cdot r$ | 存在一个在位置 $1$ 上的夸克 | | $2$ | $40\cdot r$ | 夸克的位置均为偶数 | | $3$ | $20\cdot r$ | 无额外限制 | 其中 $r$ 为一个常数。记某个子任务中你查询的最大次数为 $Q$，则 $r$ 的值见以下表格： | $Q$ 的限制 | $r=$ | | :--: | :--: | | $Q\gt 15\, 000$ | $0$ | | $15\, 000\ge Q\gt 5\, 600$ | $0.4$ | | $5\, 600\ge Q\gt 3\, 500$ | $0.6$ | | $3\, 500\ge Q\gt 2\, 400$ | $0.8$ | | $Q\le 2\, 400$ | $1.0$ | 为了方便选手测试，我们提供了 `testing_tools.py`，可在附件下载，使用说明见文件头。