CF2159A.MAD Interactive Problem

This is an interactive problem.

There is a secret sequence $a_1, a_2, \ldots, a_{2n-1},a_{2n}$, which contains each integer from $1$ to $n$ exactly twice.

Your task is to guess the sequence by using queries of the following type:

• "? $k\;j_1\;j_2\;\ldots\;j_k$" — select the integer $k$ ($1 \le k \le 2n$) and $k$ distinct indices $j_1, j_2, \ldots, j_k$ ($1 \le j_1 , j_2 , \ldots , j_k \le 2n$). In response to the query, the jury will return $\text{MAD}([a_{j_1}, a_{j_2}, \ldots, a_{j_k}])$.

We define the $\operatorname{MAD}$ (Maximum Appearing Duplicate) of an integer sequence as the largest integer that appears at least twice. Specifically, if there is no number that appears at least twice, the $\operatorname{MAD}$ value is $0$. Some examples are as follows:

• $\operatorname{MAD}([1, 2, 1]) = 1$;
• $\operatorname{MAD}([2, 2, 3, 3]) = 3$;
• $\operatorname{MAD}([1, 2, 3, 4]) = 0$.

Please identify the secret sequence using at most $3n$ queries.

这是一个交互式问题。

存在一个秘密序列 $a_1, a_2, \ldots, a_{2n-1},a_{2n}$，其中每个从 $1$ 到 $n$ 的整数恰好出现两次。

你的任务是通过以下类型的查询来推断该序列：

• “? $k\;j_1\;j_2\;\ldots\;j_k$” —— 选择一个整数 $k$（$1 \le k \le 2n$）以及 $k$ 个互不相同的下标 $j_1, j_2, \ldots, j_k$（$1 \le j_1 , j_2 , \ldots , j_k \le 2n$）。对于该查询，评测系统将返回 $\text{MAD}([a_{j_1}, a_{j_2}, \ldots, a_{j_k}])$。

我们定义一个整数序列的 $\operatorname{MAD}$（最大重复出现值）为至少出现两次的最大整数。特别地，若序列中没有任何数出现至少两次，则 $\operatorname{MAD}$ 的值为 $0$。例如：

• $\operatorname{MAD}([1, 2, 1]) = 1$；
• $\operatorname{MAD}([2, 2, 3, 3]) = 3$；
• $\operatorname{MAD}([1, 2, 3, 4]) = 0$。

请在至多 $3n$ 次查询内确定该秘密序列。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 3000$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($2 \le n \le 300$).

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

After you read this line of input, the interaction begins with your first query.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 3000$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 300$）。

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

在读入该输入行后，交互即从你的第一个查询开始。

In the first test case, the hidden sequence is $a=[2,2,1,1]$.

For the query "? 2 2 1", the jury returns $2$ because $\operatorname{MAD}([a_2, a_1]) = \operatorname{MAD}([2, 2]) = 2$.

For the query "? 2 1 3", the jury returns $0$ because $\operatorname{MAD}([a_1, a_3]) = \operatorname{MAD}([2, 1]) = 0$.

For the query "? 3 1 3 4", the jury returns $1$ because $\operatorname{MAD}([a_1, a_3, a_4]) = \operatorname{MAD}([2 ,1, 1]) = 1$.

Note that the example interaction is only for understanding statements and does not guarantee finding a unique sequence $a$.

在第一个测试用例中，隐藏序列为 $a=[2,2,1,1]$。

对于查询 "? 2 2 1"，评测系统返回 $2$，因为 $\operatorname{MAD}([a_2, a_1]) = \operatorname{MAD}([2, 2]) = 2$。

对于查询 "? 2 1 3"，评测系统返回 $0$，因为 $\operatorname{MAD}([a_1, a_3]) = \operatorname{MAD}([2, 1]) = 0$。

对于查询 "? 3 1 3 4"，评测系统返回 $1$，因为 $\operatorname{MAD}([a_1, a_3, a_4]) = \operatorname{MAD}([2 ,1, 1]) = 1$。

注意：该示例交互仅用于帮助理解题意，并不能保证唯一确定序列 $a$。