CF2168C.Intercepting Butterflies

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

Alice has an integer $x$ where $1 \le x \le 2^{15}$, which she needs to send to Bob (an astronaut on the Moon) as it is an important parameter for their secret project on the Moon.

Fortunately, Alice has a secret storage device $S$, which contains a not necessarily non-empty subset of the set ${1, 2, \ldots, 20}$. She plans to send $S$ to Bob. Bob's goal is to recover the value of $x$ using only $S$.

However, after Alice sends set $S$ on a spaceship and before Bob receives $S$, magical butterflies had intercepted the spaceship! When Bob finally receives $S$, one of the following had occurred:

• An arbitrary element is removed from $S$. This can only be done if $S$ is non-empty.
• An arbitrary element is added to $S$. This should still satisfy $S \subseteq {1, 2, \ldots, 20}$.
• $S$ remained unchanged.

Please devise a strategy for Alice and Bob so that Bob can determine the value of $x$ regardless of what happened to set $S$. Precisely, in this problem your code will be run exactly two times on each test. On the first run, you will act as Alice, and on the second Bob. No additional information other than the set $S$ can be transferred from Alice to Bob. To get an Accepted verdict, your code on the second run should be able to exactly recover the integers that were received on the first run.

First Run

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 Alice.

The second line of the input contains exactly one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first and only line of the $i$-th test case contains an integer $x$ ($1 \le x \le 2^{15}$).

Output

For each test case, send $S$ to Bob by printing two lines in the following manner.

• On the first line, output an integer $n$ ($0 \le n \le 20$) — the size of $S$.
• On the second line, output $n$ space-separated integers $S_1,S_2,\ldots,S_n$ ($1 \le S_i \le 20$).

Exceptionally, you may omit the second line if $n=0$. You may output elements of $S$ in any order. However, they must be pairwise distinct.

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

Second Run

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 Bob.

The second line of the input contains exactly one integer $t$ ($1 \le t \le 10^4$) — 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 an integer $n'$ ($0 \leq n' \leq 20$) — the size of the set $S'$ that Bob receives, that is, possibly modified $S$.

The second line of each test case contains $n$ integers $S'_1, S'_2, \ldots, S'_n$ ($1 \leq S'_i \leq 20$) — the elements of the $S'$ that Bob receives. The elements of $S'$ are sorted in increasing order, even if the original $S$ is not sorted in increasing order.

Note that the test cases in the second run may be shuffled. Please see the example input for more details.

Output

For each test case, print a single line with the value of $x$ ($1 \leq x \leq 2^{15}$).

本题是一个“运行两次”（通信）问题。

爱丽丝拥有一个整数 $x$，满足 $1 \le x \le 2^{15}$，她需要将该整数发送给鲍勃（一位身处月球的宇航员），因为这是他们月球秘密项目的一个关键参数。

幸运的是，爱丽丝拥有一台秘密存储设备 $S$，其中存储了集合 $\{1, 2, \ldots, 20\}$ 的一个不一定非空的子集。她计划将该集合 $S$ 发送给鲍勃。鲍勃的目标是仅利用接收到的 $S$ 恢复出 $x$ 的值。

然而，在爱丽丝将集合 $S$ 装载于飞船并发出之后、鲍勃实际接收到 $S$ 之前，一群魔法蝴蝶劫持了这艘飞船！当鲍勃最终收到 $S$ 时，以下三种情况之一必然发生：

• $S$ 中被任意移除了一个元素（仅当 $S$ 非空时才可能发生）；
• 向 $S$ 中任意添加了一个元素（添加后仍需满足 $S \subseteq \{1, 2, \ldots, 20\}$）；
• $S$ 完全未被改动。

请为爱丽丝和鲍勃设计一种策略，使得无论 $S$ 经历了上述哪一种变化，鲍勃均能准确确定 $x$ 的值。具体而言，本题中你的代码将在每个测试用例上恰好运行两次：第一次运行时你扮演爱丽丝，第二次运行时你扮演鲍勃。除集合 $S$ 外，爱丽丝无法向鲍勃传递任何额外信息。要获得“Accepted”判定，你在第二次运行时输出的整数必须与第一次运行时输入的整数完全一致。

第一次运行（爱丽丝）

输入

第一行包含字符串 first，用于提示你的程序当前处于第一次运行阶段，应作为爱丽丝执行。

第二行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

第 $i$ 个测试用例仅有一行，包含一个整数 $x$（$1 \le x \le 2^{15}$）。

输出

对每个测试用例，按如下方式输出两行，以将集合 $S$ 发送给鲍勃：

• 第一行输出一个整数 $n$（$0 \le n \le 20$）——即集合 $S$ 的大小；
• 第二行输出 $n$ 个以空格分隔的整数 $S_1, S_2, \ldots, S_n$（$1 \le S_i \le 20$）。

特别地，若 $n = 0$，可省略第二行。你可以以任意顺序输出 $S$ 的元素，但所有元素必须两两互异。

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

第二次运行（鲍勃）

输入

第一行包含字符串 second，用于提示你的程序当前处于第二次运行阶段，应作为鲍勃执行。

第二行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。注意：该数值与第一次运行输入中的 $t$ 相同。

每个测试用例的第一行包含一个整数 $n'$（$0 \leq n' \leq 20$）——即鲍勃所接收的集合 $S'$ 的大小，该集合是可能已被修改过的 $S$。

每个测试用例的第二行包含 $n'$ 个整数 $S'_1, S'_2, \ldots, S'_{n'}$（$1 \leq S'_i \leq 20$）——即鲍勃所接收的集合 $S'$ 的元素。注意：$S'$ 的元素按升序排列，即使原始 $S$ 并非升序。

注意：第二次运行中的测试用例顺序可能被随机打乱。更多细节请参见样例输入。

输出

对每个测试用例，输出一行，内容为整数 $x$（$1 \leq x \leq 2^{15}$）。

First run: The input contains four test cases with $x=1, 20, 50, 32\,768$. According to some strategy agreed upon beforehand, Alice sends $\varnothing$ to Bob for $x=1$, the set ${13,4,9}$ for $x=20$, the set ${1,7,4,2}$ for $x=50$, and ${14,17,1,6,2,19,20,8,7,18}$ for $32\,768$.

Second run: Note that the test cases from the first run are shuffled. They are given in the order $[20, 32\,768, 1, 50]$.

For the first test case, the element $5$ is added to Alice's set. Note that although Alice gave the initial set as ${13,4,9}$, the set was given in increasing order to Bob.

For the second test case, the number $20$ was removed from Alice's set.

For the third test case, the set was unchanged.

第一次运行：输入包含四个测试用例，对应的 $x$ 值分别为 $1$、$20$、$50$ 和 $32\,768$。根据事先约定的某种策略，Alice 对 $x=1$ 向 Bob 发送 $\varnothing$；对 $x=20$ 发送集合 ${13,4,9}$；对 $x=50$ 发送集合 ${1,7,4,2}$；对 $x=32\,768$ 发送集合 ${14,17,1,6,2,19,20,8,7,18}$。

第二次运行：注意，第一次运行中的测试用例顺序已被打乱，现以 $[20, 32\,768, 1, 50]$ 的顺序给出。

对于第一个测试用例（即 $x=20$），元素 $5$ 被加入 Alice 的集合中。注意，尽管 Alice 最初给出的集合为 ${13,4,9}$，但该集合是以升序形式提供给 Bob 的。

对于第二个测试用例（即 $x=32\,768$），数字 $20$ 从 Alice 的集合中被移除。

对于第三个测试用例（即 $x=1$），集合保持不变。