CF2237G.Send GCDs

This is a run-twice (communication) interactive problem.

There are two players: Ja the Ghost and Quack the Duck. The jury (otherwise known as the interactor of this problem) will first interact with Ja. After Ja ends the interaction, the jury will interact with Quack. Note that Ja and Quack may not directly pass information to each other; both players are only able to send information to or receive information from the jury.

Before the interaction, the jury determines an integer $n$ and an array of $n$ positive integers $a_1, a_2, \ldots, a_n$. These values are consistent across both players.

Ja receives $n$ and an array of $n$ positive integers $a_1, a_2, \ldots, a_n$ from the jury, which he wants to send to Quack, where $a_i \le 10^6$. To do this, Ja will select an integer $k$, where $$k \le \left\lceil \frac{10n}{9} \right\rceil + 150,$$ and create an array of positive integers $b_1, b_2, \ldots, b_k$, where $b_i \le 10^6$, and send it back to the jury. Then the jury will give Quack the integers $n$ and $k$. Quack can ask the jury at most $180n + 150$ queries in the following form:

• Choose any two integers $i$ and $j$ ($1 \le i, j \le k$, $i \neq j$), and the jury will respond with $\mathrm{gcd}(b_i, b_j)$.

Here, $\gcd(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$.

Note that both $a$ and $b$ are hidden from Quack; Quack can only get information from queries.

Ja wants to ensure that Quack can determine the original array $a$. Your task is to act as both players and determine an optimal interaction strategy for both players so that Quack determines the original array $a$ correctly.

First Run

Your code will run exactly twice on each test. On the first run, you will be Ja.

Input

The first line of the input contains the string first. The purpose of this is so your program recognizes that this is its first run, and it should act as Ja.

The second line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line of the $i$-th test case contains an integer $n$ ($1 \le n \le 10^3$) — the length of $a$ for the $i$-th test case.

The second line of the $i$-th test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$) — the array $a$.

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

Output

For each test case, first print an integer $k$ ($1 \le k \le \left\lceil \frac{10n}{9} \right\rceil + 150$), denoting the length of the array $b$. Then print $k$ integers $b_1, b_2, \ldots, b_k$ ($1 \le b_i \le 10^6$), denoting the array $b$ that Ja will send to the jury. This array will be used to answer the queries in the second run.

After this, proceed to the next test case or terminate your program if it was the last test case.

Second Run

On the second run, you are Quack.

Input

The first line of the input contains the string second. The purpose of this is so your program recognizes that this is its second run, and it should act as Quack.

The second line of the input contains exactly one integer $t$ ($1 \le t \le 100$) — the number of test cases. Note that this number is equal to $t$ from the first run input.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 10^3$, $1 \le k \le \left\lceil \frac{10n}{9} \right\rceil + 150$). This denotes the lengths of $a$ and $b$, respectively.

Note that the test cases in the second run may be shuffled. Please see the example test case for further illustration.

Interaction

For the $i$-th test case, recall that you will first receive $n$ and $k$ in the input from the jury according to the input format above. After receiving those inputs, you will be able to make at most $180n + 150$ queries of the following form:

• ? i j ($1 \leq i, j \leq k$, $i \neq j$).

After each query, the jury will respond with $\mathrm{gcd}(b_i, b_j)$, which you should read through the input stream.

If your program makes more than $180n + 150$ queries, your program should immediately terminate and receive the verdict Wrong Answer. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

Once you are ready to report the original array $a$, you may do so in the following format:

• ! $a_1, a_2, \ldots ,a_n$ ($1 \leq a_i \leq 10^6$).

Then, you will either proceed to the next test case, or your program must terminate if you have processed every test case.

The interactor is not adaptive. That is, both arrays $a$ and $b$ will not change during the interaction and will always be the same arrays as in the first run.

After printing each query do not forget to output the end of line and flush$^{\text{∗}}$ the output. Otherwise, you will get Idleness limit exceeded verdict.

If, at any interaction step, you read $-1$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

$^{\text{∗}}$To flush, use:

• fflush(stdout) or cout.flush() in C++;
• sys.stdout.flush() in Python;
• see the documentation for other languages.

这是一个需运行两次（通信）的交互式问题。

有两个玩家：幽灵杰（Ja the Ghost）和鸭子夸克（Quack the Duck）。评测系统（即本题的交互器）首先与杰交互；杰结束交互后，评测系统再与夸克交互。注意：杰与夸克之间不能直接传递信息；双方仅能向评测系统发送信息或从评测系统接收信息。

在交互开始前，评测系统会确定一个整数 $n$ 和一个由 $n$ 个正整数构成的数组 $a_1, a_2, \ldots, a_n$。这些值在两轮交互中保持一致。

杰从评测系统处接收 $n$ 和一个由 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ 构成的数组（其中 $a_i \le 10^6$），他需要将该数组完整地传递给夸克。为此，杰将选择一个整数 $k$，满足

$$k \le \left\lceil \frac{10n}{9} \right\rceil + 150,$$

并构造一个由 $k$ 个正整数 $b_1, b_2, \ldots, b_k$（其中 $b_i \le 10^6$）组成的数组，将其回传给评测系统。随后，评测系统将把整数 $n$ 和 $k$ 提供给夸克。夸克最多可向评测系统发起 $180n + 150$ 次如下形式的查询：

• 任选两个整数 $i$ 和 $j$（$1 \le i, j \le k$，且 $i \neq j$），评测系统将返回 $\mathrm{gcd}(b_i, b_j)$。

此处 $\gcd(x, y)$ 表示整数 $x$ 与 $y$ 的最大公约数（GCD）。

注意：数组 $a$ 和 $b$ 对夸克均是隐藏的；夸克只能通过查询获取信息。

杰的目标是确保夸克能够准确还原原始数组 $a$。你的任务是同时扮演两名玩家，为双方设计一种最优交互策略，使得夸克能正确还原原始数组 $a$。

第一轮运行

你的代码将在每个测试用例上恰好运行两次。第一次运行时，你扮演杰。

输入

输入的第一行是一个字符串 first，用于提示你的程序：当前为第一轮运行，应以杰的身份执行。

第二行包含测试用例数量 $t$（$1 \le t \le 100$）。随后是各测试用例的描述。

第 $i$ 个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^3$）——表示该测试用例中数组 $a$ 的长度。

第 $i$ 个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^6$）——即数组 $a$。

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

输出

对每个测试用例，首先输出一个整数 $k$（$1 \le k \le \left\lceil \frac{10n}{9} \right\rceil + 150$），表示数组 $b$ 的长度；然后输出 $k$ 个整数 $b_1, b_2, \ldots, b_k$（$1 \le b_i \le 10^6$），即杰发送给评测系统的数组 $b$。该数组将在第二轮运行中用于响应查询。

之后进入下一个测试用例，或若已处理完全部测试用例，则终止程序。

第二轮运行

第二次运行时，你扮演夸克。

输入

输入的第一行是一个字符串 second，用于提示你的程序：当前为第二轮运行，应以夸克的身份执行。

输入的第二行恰好包含一个整数 $t$（$1 \le t \le 100$）——测试用例数量。注意：该数值与第一轮输入中的 $t$ 相同。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 10^3$，$1 \le k \le \left\lceil \frac{10n}{9} \right\rceil + 150$），分别表示数组 $a$ 和 $b$ 的长度。

注意：第二轮中的测试用例顺序可能被随机打乱。请参见样例测试用例以获得进一步说明。

交互过程

对于第 $i$ 个测试用例，你将首先根据上述输入格式从评测系统处接收 $n$ 和 $k$。接收完毕后，你最多可发起 $180n + 150$ 次如下形式的查询：

• ? i j（其中 $1 \leq i, j \leq k$，且 $i \neq j$）。

每次查询后，评测系统将返回 $\mathrm{gcd}(b_i, b_j)$，你需要从输入流中读取该值。

若你的程序发起的查询次数超过 $180n + 150$ 次，程序必须立即终止，并被判为“答案错误（Wrong Answer）”。否则，由于程序将继续从已关闭的输入流中读取数据，你可能收到任意错误判定。

当你准备好报告原始数组 $a$ 时，可按如下格式输出：

• ! a_1 a_2 ... a_n（其中 $1 \leq a_i \leq 10^6$）。

随后，你将进入下一个测试用例；若所有测试用例均已处理完毕，则必须终止程序。

本交互器是非自适应的（non-adaptive）。即：在整个交互过程中，数组 $a$ 和 $b$ 均不会改变，且始终与第一轮运行中使用的数组完全相同。

每次输出查询后，请务必输出换行符并刷新输出流$^{\text{∗}}$；否则将收到“空闲超限（Idleness limit exceeded）”判定。

若在交互过程中的任意时刻，你从输入流中读取到 $-1$（而非合法数据），你的程序必须立即退出。这意味着你的解法因非法查询或其他错误而被判为“答案错误（Wrong Answer）”。未及时退出可能导致任意错误判定，因为程序将继续尝试从已关闭的输入流中读取数据。

$^{\text{∗}}$刷新输出的方法如下：

• C++ 中使用 fflush(stdout) 或 cout.flush()；
• Python 中使用 sys.stdout.flush()；
• 其他语言请参考相应文档。

null

null

In the first run, there are two test cases.

For the first test case, Ja is given $a = [1, 1, 4, 5, 1, 4]$. He decides to send $b = [20, 1, 1, 4, 5, 1, 4]$.

For the second test case, Ja is given $a = [2, 6, 10]$. He decides to send $b = [30, 2, 6, 10]$.

In the second run, the order of the test cases is shuffled. Therefore, Quack first receives the test case with $n = 3$ and $k = 4$. He asks $\mathrm{gcd}(b_1, b_i)$ for $i = 2, 3, 4$, and the jury answers $2, 6, 10$. Thus, Quack can determine that the original array is $[2, 6, 10]$.

Then Quack receives the test case with $n = 6$ and $k = 7$. He asks $\mathrm{gcd}(b_1, b_i)$ for $i = 2, 3, 4, 5, 6, 7$, and the jury answers $1, 1, 4, 5, 1, 4$. Thus, Quack can determine that the original array is $[1, 1, 4, 5, 1, 4]$.

This example illustrates that although the test cases in the second run may appear in a different order, the same arrays $a$ and $b$ from the first run are used.

第一次运行中，共有两个测试用例。

对于第一个测试用例，Ja 被给定数组 $a = [1, 1, 4, 5, 1, 4]$，他决定发送数组 $b = [20, 1, 1, 4, 5, 1, 4]$。

对于第二个测试用例，Ja 被给定数组 $a = [2, 6, 10]$，他决定发送数组 $b = [30, 2, 6, 10]$。

在第二次运行中，测试用例的顺序被打乱。因此，Quack 首先收到 $n = 3$ 且 $k = 4$ 的测试用例。他询问 $\mathrm{gcd}(b_1, b_i)$（其中 $i = 2, 3, 4$），裁判回答为 $2, 6, 10$。于是 Quack 可以确定原始数组为 $[2, 6, 10]$。

接着，Quack 收到 $n = 6$ 且 $k = 7$ 的测试用例。他询问 $\mathrm{gcd}(b_1, b_i)$（其中 $i = 2, 3, 4, 5, 6, 7$），裁判回答为 $1, 1, 4, 5, 1, 4$。于是 Quack 可以确定原始数组为 $[1, 1, 4, 5, 1, 4]$。

该示例说明：尽管第二次运行中的测试用例顺序可能不同，但使用的仍是第一次运行中的相同数组 $a$ 和 $b$。