题目背景

译自 Nordic Olympiad in Informatics 2022 Quark Microscopy。如果发现交互库锅了请联系搬题人 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 3

6 1

4 1

1 2

? 5

? 15

? 11

! 11 10 12

3 1

2 1

1 2

2 1

45 1

? 1

? 2

? 3

? 47

! 1 3 92

提示

数据范围

• $3\le N\le 100$；
• $1\le T\le 3$。

评分方式

其中 $r$ 为一个常数。记某个子任务中你查询的最大次数为 $Q$，则 $r$ 的值见以下表格：

为了方便选手测试，我们提供了 testing_tools.py，可在附件下载，使用说明见文件头。