CF1807E.Interview

This is an interactive problem. If you are unsure how interactive problems work, then it is recommended to read the guide for participants.

Before the last stage of the exam, the director conducted an interview. He gave Gon $n$ piles of stones, the $i$-th pile having $a_i$ stones.

Each stone is identical and weighs $1$ grams, except for one special stone that is part of an unknown pile and weighs $2$ grams.

A picture of the first test case. Pile $2$ has the special stone. The piles have weights of $1,3,3,4,5$, respectively.

Gon can only ask the director questions of one kind: he can choose $k$ piles, and the director will tell him the total weight of the piles chosen. More formally, Gon can choose an integer $k$ ($1 \leq k \leq n$) and $k$ unique piles $p_1, p_2, \dots, p_k$ ($1 \leq p_i \leq n$), and the director will return the total weight $m_{p_1} + m_{p_2} + \dots + m_{p_k}$, where $m_i$ denotes the weight of pile $i$.

Gon is tasked with finding the pile that contains the special stone. However, the director is busy. Help Gon find this pile in at most $\mathbf{30}$ queries.

这是一个交互式问题。如果你不确定交互式问题的工作方式，建议先阅读参赛者指南。

在考试最后一阶段之前，校长进行了一次面试。他给了 Gon $n$ 堆石头，其中第 $i$ 堆有 $a_i$ 颗石头。

每颗石头均相同，重量均为 $1$ 克，但其中有一颗特殊石头例外：它属于某堆未知的石头，重量为 $2$ 克。

第一个测试用例示意图。第 $2$ 堆包含特殊石头。各堆重量分别为 $1,3,3,4,5$。

Gon 只能向校长提出一种类型的问题：他可以选择 $k$ 堆石头，校长会告诉他所选各堆石头的总重量。更准确地说，Gon 可以选择一个整数 $k$（满足 $1 \leq k \leq n$）以及 $k$ 个互不相同的堆编号 $p_1, p_2, \dots, p_k$（满足 $1 \leq p_i \leq n$），校长将返回总重量 $m_{p_1} + m_{p_2} + \dots + m_{p_k}$，其中 $m_i$ 表示第 $i$ 堆的总重量。

Gon 的任务是找出包含特殊石头的那一堆。然而，校长很忙。请帮助 Gon 在至多 $\mathbf{30}$ 次询问内找到该堆。

The input data contains several test cases. The first line contains one integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of piles.

The second line of each test case contains $n$ integers $a_i$ ($1 \leq a_i \leq 10^4$) — the number of stones in each pile.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

After reading the input for each test case, proceed with the interaction as follows.

输入数据包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示石堆的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_i$（$1 \leq a_i \leq 10^4$），表示每堆石子的数量。

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

读取每个测试用例的输入后，按如下方式与交互系统进行交互。

In the first test case, the stone with weight two is located in pile $2$, as shown in the picture. We perform the following interaction:

• $\texttt{? 4 1 2 3 4}$ — ask the total weight of piles $1$, $2$, $3$, and $4$. The total weight we receive back is $1+3+3+4=11$.
• $\texttt{? 2 2 3}$ — ask the total weight of piles $2$ and $3$. The total weight we receive back is $3+3=6$.
• $\texttt{? 1 2}$ — ask the total weight of pile $2$. The total weight we receive back is $3$.
• $\texttt{! 2}$ — we have figured out that pile $2$ contains the special stone, so we output it and move on to the next test case.

In the second test case, the stone with weight two is located on index $7$. We perform the following interaction:

• $\texttt{? 4 2 3 5 6}$ — ask the total weight of piles $2$, $3$, $5$, and $6$. The total weight we receive back is $2+3+3+4=12$.
• $\texttt{? 2 1 4}$ — ask the total weight of piles $1$ and $4$. The total weight we receive back is $1+5=6$.
• $\texttt{! 7}$ — we have somehow figured out that pile $7$ contains the special stone, so we output it and end the interaction.

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

• $\texttt{? 4 1 2 3 4}$ —— 查询第 $1$、$2$、$3$、$4$ 堆的总重量。返回的总重量为 $1+3+3+4=11$。
• $\texttt{? 2 2 3}$ —— 查询第 $2$、$3$ 堆的总重量。返回的总重量为 $3+3=6$。
• $\texttt{? 1 2}$ —— 查询第 $2$ 堆的总重量。返回的总重量为 $3$。
• $\texttt{! 2}$ —— 我们已确定第 $2$ 堆包含特殊石子，因此输出 $2$ 并进入下一个测试用例。

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

• $\texttt{? 4 2 3 5 6}$ —— 查询第 $2$、$3$、$5$、$6$ 堆的总重量。返回的总重量为 $2+3+3+4=12$。
• $\texttt{? 2 1 4}$ —— 查询第 $1$、$4$ 堆的总重量。返回的总重量为 $1+5=6$。
• $\texttt{! 7}$ —— 我们已确定第 $7$ 堆包含特殊石子，因此输出 $7$ 并结束交互。