这个问题是一个运行两次(通信)问题。
Alice有一个整数$$$x$$$,其中$$$1 \le x \le 2^{15}$$$,她需要将其发送给Bob(月球上的宇航员),因为这是他们在月球上的秘密项目的重要参数。
幸运的是,Alice 有一个秘密存储设备 $$$S$$$,其中包含 不一定非空 集合 $$$\{1, 2, \ldots, 20\}$$$ 的子集。她计划向 Bob 发送 $$$S$$$。 Bob 的目标是仅使用 $$$S$$$ 恢复 $$$x$$$ 的值。
然而,在爱丽丝在宇宙飞船上发送了$$$S$$$之后,鲍勃收到$$$S$$$之前,魔法蝴蝶已经拦截了宇宙飞船!当 Bob 最终收到 $$$S$$$ 时,发生了以下情况之一:
- 从 $$$S$$$ 中删除任意元素。仅当 $$$S$$$ 非空时才能执行此操作。
- 任意元素被添加到$$$S$$$。这仍然应该满足 $$$S \subseteq \{1, 2, \ldots, 20\}$$$。
- $$$S$$$ 保持不变。
请为 Alice 和 Bob 设计一个策略,以便 Bob 可以确定 $$$x$$$ 的值,无论设置 $$$S$$$ 时发生了什么。准确地说,在这个问题中,您的代码将在每个测试中运行两次。在第一次运行中,您将扮演爱丽丝,在第二次运行中,您将扮演鲍勃。除了 $$$S$$$ 集合之外,没有其他信息可以从 Alice 传输到 Bob。为了得到一个 已接受 结论,第二次运行的代码应该能够准确恢复第一次运行时收到的整数。
首次运行
输入
输入的第一行包含字符串 第一。这样做的目的是让您的程序认识到这是它的第一次运行,并且它应该充当 Alice。
输入的第二行恰好包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
第 $$$i$$$ 测试用例的第一行也是唯一一行包含整数 $$$x$$$ ($$$1 \le x \le 2^{15}$$$)。
输出
对于每个测试用例,通过按以下方式打印两行将 $$$S$$$ 发送给 Bob。
- 在第一行,输出一个整数 $$$n$$$ ($$$0 \le n \le 20$$$) — $$$S$$$ 的大小。
- 在第二行,输出 $$$n$$$ 空格分隔的整数 $$$S_1,S_2,\ldots,S_n$$$ ($$$1 \le S_i \le 20$$$)。
特殊情况下,如果 $$$n=0$$$,则可以省略第二行。您可以按任意顺序输出 $$$S$$$ 的元素。然而,它们必须是成对不同的。
然后,您将继续执行下一个测试用例,或者如果您已处理完每个测试用例,则程序必须终止。
第二次运行
输入
输入的第一行包含字符串 第二。这样做的目的是让您的程序认识到这是它的第二次运行,并且它应该充当 Bob。
输入的第二行恰好包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。请注意,该数字等于第一次运行输入中的 $$$t$$$。
每个测试用例的第一行包含一个整数 $$$n'$$$ ($$$0 \leq n' \leq 20$$$) - Bob 收到的集合 $$$S'$$$ 的大小,即可能 已修改 $$$S$$$。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$S'_1, S'_2, \ldots, S'_n$$$ ($$$1 \leq S'_i \leq 20$$$) — Bob 收到的 $$$S'$$$ 的元素。 $$$S'$$$ 的元素按升序排序,即使原始 $$$S$$$ 未按升序排序。
请注意,第二次运行中的测试用例可能会被打乱。请参阅示例输入了解更多详细信息。
输出
对于每个测试用例,打印一行,其值为 $$$x$$$ ($$$1 \leq x \leq 2^{15}$$$)。
示例
输入复制
first 4 1 20 50 32768
输出复制
0 3 13 4 9 4 1 7 4 2 10 14 17 1 6 2 19 20 8 7 18
输入复制
second 4 4 4 5 9 13 9 1 2 6 7 8 14 17 18 19 0 5 1 2 3 4 7
输出复制
20 32768 1 50
注意
首次运行:输入包含四个测试用例,$$$x=1, 20, 50, 32\,768$$$。根据事先约定的策略,Alice 将 $$$x=1$$$ 发送给 Bob $$$\varnothing$$$,$$$x=20$$$ 的集合 $$$\{13,4,9\}$$$,$$$x=20$$$ 的集合 $$$\{1,7,4,2\}$$$,$$$x=50$$$ 的集合 $$$\{1,7,4,2\}$$$,以及$$$\{14,17,1,6,2,19,20,8,7,18\}$$$ 为 $$$32\,768$$$。
第二次运行:请注意,第一次运行的测试用例被打乱了。它们按 $$$[20, 32\,768, 1, 50]$$$ 的顺序给出。
对于第一个测试用例,元素 $$$5$$$ 被添加到 Alice 的集合中。请注意,虽然 Alice 给出的初始集合为 $$$\{13,4,9\}$$$,但该集合是按递增顺序给出给 Bob 的。
对于第二个测试用例,数字 $$$20$$$ 已从 Alice 的集合中删除。
对于第三个测试用例,该集合未更改。