题目描述

这是一个交互式问题。

你面前有一批 $n$ 枚金币，其中有 $k$ 枚是假币。所有金币排成一行。第 $i$ 枚金币的理论重量为 $i$ 克。如果某枚金币是假币，它的重量为 $0$ 克。

禁止触碰金币，你唯一能进行的操作是选择某个 $1 \leq p \leq n$，称为称重操作，对前 $p$ 枚金币进行称重。你将得到这 $p$ 枚金币的真实总重量。

请你用尽量少的操作，找出哪 $k$ 枚金币是假币。你做的称重次数越少，得分越高，具体请见评分说明。

交互说明

每个测试包含 $t$ 局游戏，你需要在每局中找出哪些金币是假币。输入的第一行包含一个整数 $t$（$1 \leq t \leq 50$），表示游戏的局数。每局的交互格式如下。所有局结束后，你的程序应当终止。

每局开始时，给出两个整数 $n$ 和 $k$（$1 \leq n \leq 10^9$，$1 \leq k \leq \min(100, n)$）。此后你可以进行多次称重操作。

要进行一次称重操作，输出 ? p（注意空格），表示你要称重前 $p$ 枚金币。你将获得一个整数 $a$。如果 $a = -1$，说明你已经超过了本局允许的最大称重次数，你的程序必须立即终止。每局最多允许 $3500$ 次称重。若 $a \geq 0$，则 $a$ 是金币 $1, 2, \ldots, p$ 的真实总重量。

当你确定了假币的位置后，输出 $!\ i_1\ i_2\ \ldots\ i_k$，其中 $1 \leq i_1, i_2, \ldots, i_k \leq n$ 且互不相同，表示你认为是假币的编号，顺序任意。此后你会收到一个整数 $a$。如果 $a = -1$，说明你的答案错误，你的程序必须立即终止。否则 $a = 1$，表示答案正确，你应继续进行下一局或终止（如果这是最后一局）。

注意，交互器是自适应的。并不保证每局假币的位置在游戏开始前就已确定。唯一保证的是，交互器给出的所有称重结果，在任何时刻都与某个假币集合相符。你的答案是正确的，如果它与所有你收到的称重结果一致，且不存在另一个假币集合也能与所有称重结果一致。

每次输出后请输出换行符，并刷新输出缓冲区。

如果你使用 Pascal 的 writeln，C++ 的 cout << ... << endl，Java 的 System.out.println，Python 的 print，C# 的 Console.WriteLine，则会自动刷新缓冲区，无需特殊处理。如果你使用其他输出方式，建议手动刷新。无论如何，每次输出都要换行。

2
3 2

2

1
10 4

13

13

20

29

1

? 3

! 1 3


? 5

? 6

? 8

? 10

! 10 8 6 2

提示

样例解释

在第一局中，金币 $1$ 和 $3$ 是假币，因此实际重量为 $[0, 2, 0]$。只需一次称重即可得到总重量 $2$，据此可以唯一确定假币的位置。

在第二局中，金币 $2, 6, 8, 10$ 是假币，实际重量为 $[1, 0, 3, 4, 5, 0, 7, 0, 9, 0]$。通过称重结果可以唯一确定假币集合。

评分说明

本题测试点分为 6 组。设 $q$ 为你在一局中称重的次数。

前 5 组，每组有一个 $maxQ$，如果你在一局中 $q \leq maxQ$，则该测试点通过。只有通过某组全部测试点，且通过部分之前组全部测试点，才能获得该组分数。

第 6 组为部分分，单局得分为 $\min\left(50, \left\lfloor 50 \sqrt{\frac{k + 30}{q}} \right\rfloor\right)$。该组的总分为所有测试中单局得分的最小值。

注意：如果你在所有测试的所有局中都能做到 $q \leq k + 30$，则可获得 $100$ 分。

组别	分值	$n$	$k$	$maxQ$	必须通过的组	备注
0		--	--	$3500$	--	样例测试点
1	5	$n \leq 1000$		$1000$	0
2	9			$600$	0, 1
3	10	--	$k \leq 30$	$1000$	0
4	13		$k = 3$	$33$	--
5			$k = 4$	$34$
6	$\leq 50$		--	$3500$		部分分数