Description

我有一个正整数集合 $\mathbf{S}$。你能否找到两个非空且不同的子集，使它们的元素和相等？

注意：子集是仅包含自 $\mathbf{S}$ 的元素的集合；若两个子集包含的元素完全相同，则认为它们是相同的，否则为不同子集。

Input Format

输入的第一行为测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试数据，每组一行。每组数据首先给出一个整数 $\mathbf{N}$，表示集合 $\mathbf{S}$ 中正整数的个数，随后是 $\mathbf{N}$ 个互不相同的正整数，全部在同一行。

Output Format

对于每个测试用例，首先输出一行 "Case #x:"，其中 $\mathbf{x}$ 为测试用例编号（从 1 开始）。

• 如果存在 $\mathbf{S}$ 的两个不同子集，其元素和相等，则输出这两个子集，每行一个子集，子集内元素以空格分隔。
• 如果不存在这样的子集，则输出一行 "Impossible"。

如果存在多组答案，输出任意一组均可。注意原题样例没有输出方案。

2
20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20 120 266 858 1243 1657 1771 2328 2490 2665 2894 3117 4210 4454 4943 5690 6170 7048 7125 9512 9600

Case #1: Possible
Case #2: Possible

Hint

限制条件

• $\mathbf{S}$ 中不会有相同的数。
• $1 \leq \mathbf{T} \leq 10$。

测试集 1（6 分，结果可见）

• 时间限制：60 12 秒。
• $\mathbf{N}$ 恰好等于 $20$。
• $\mathbf{S}$ 中每个数均为小于 $10^5$ 的正整数。

测试集 2（37 分，结果隐藏）

• 时间限制：120 30 秒。
• $\mathbf{N}$ 恰好等于 $500$。
• $\mathbf{S}$ 中每个数均为小于 $10^{12}$ 的正整数。

翻译由 ChatGPT-4.1 完成。