题目描述

这是一个交互式问题。

在面试 $Macrohard$ 的最后阶段，大老板 $Bull\ Doors$ 进行了一次面试。他给了你 $n$ 堆石头，第 $i$ 堆有 $a_i$ 块石头。

除了一块特殊的石头重 $2$ 克外，每一块石头都是一样的，重 $1$ 克。

第一个测试用例的图片。堆2有特殊的石头。这些堆的重量分别为 $1$、$3$、$3$、$4$、$5$。

你可以向大老板提一种问题：选择 $k$ 个堆，大老板会告诉你这些堆的总重量。更正式地说，你可以选择一个整数 $k(1≤k≤n)$ 和 $k$ 个不同的堆 $p_1,p_2,…,p_k(1≤p_i≤n)$，大老板将告诉你总重量 $m_{p_1}+m_{p_2}+…+m_{p_k}$，其中 $m_i$ 表示第 $i$ 堆的重量。

你的任务是找到装有特殊石头的那堆石头。然而，大老板很忙。你需要在最多 $20$ 次查询中找到这一堆。

输入格式

输入数据包含几个测试用例。第一行包含一个整数 $t(1≤t≤1000)$ ——测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n(1≤n≤2×10^5)$ ——堆数。

每个测试用例的第二行包含 $n$ 个整数 $a_i(1≤a_i≤10^4)$ ——每个堆中的石头数量。

保证所有测试用例的 $n$ 之和不超过 $2×10^5$。

在读取了每个测试用例的输入之后，你可以用以下方式进行交互。

交互方式

您最多可以执行 20 次询问来确定在哪一组。

要进行询问，请使用以下格式输出一行：

? k p1 p2 p3...pk−1 pk

$(1≤k≤n;1≤p_i≤n)$ ，这里 $p_i$ 是堆的编号，互不相同。

每次询问后，后台程序将输出一个整数 $x$，即所选堆的重量之和，您应当读取这个数据。

当你确信包含特殊石头的堆的编号时，按以下格式输出一行：！m $(1≤m≤n)$。

之后，继续下一个测试用例，如果没有剩余的测试用例，则终止程序。

如果您的程序对一个测试用例执行了超过 20 次操作或进行了无效查询，您可能会收到 WA 的结果。

如果你的输出带有缓冲，输出查询指令或答案指令后，请记住刷新输出。否则，您可能会超时。要执行此操作，请使用以下操作：

C++ 中的 fflush(stdout) 或 cout.flush()；

Java 中的 System.out.flush()；

Python 中的 stdout.flush()；

测试样例

2
5
1 2 3 4 5

11

6

3

7
1 2 3 5 3 4 2

12

6

? 4 1 2 3 4

? 2 2 3

? 1 2

! 2

? 4 2 3 5 6

? 2 1 4

! 7

样例说明

在第一个测试案例中，重量为 $2$ 的石头位于第 $2$ 堆中，如图所示。我们执行以下交互：

? 4 1 2 3 4

-询问 $1,2,3,4$ 堆的总重量。我们收到的总重量是 $1+3+3+4=11$。

? 2 2 3

-询问第 $2$ 堆和第 $3$ 堆的总重量。我们收到的总重量是 $3+3=6$。

? 1 2

-询问第 $2$ 堆的总重量。我们收到的总重量是 $3$。

! 2

-我们已经发现第 $2$ 堆包含特殊的石头，所以我们输出它并继续下一个测试用例。

在第二个测试案例中，重量为 $2$ 的石头位于索引 $7$上。我们执行以下交互：

? 4 2 3 5 6

-询问第 $2,3,5,6$ 堆的总重量。我们收到的总重量是 $2+3+3+4=12$。

? 2 1 4

-询问第 $1$ 堆和第 $4$ 堆的总重量。我们收到的总重量是 $1+5=6$。

! 7

-不知怎么的，我们已经发现第 $7$ 堆含有特殊的石头，所以我们输出它并结束交互。

注意

为节省计算资源，本题时限1s，Java建议使用 PrintWriter 进行快写。