Equal Subset Sums (Small)

You are given a set $S$ of $N$ distinct positive integers. Find two non-empty subsets of $S$ that are different and whose elements add up to the same sum.

A subset is a set built only from elements of $S$. Two subsets are different when they do not hold exactly the same elements. The two subsets may share elements.

The first line holds the number of test cases $T$. Each of the next $T$ lines holds one test case. A line starts with $N$, the number of elements of $S$, followed by the $N$ distinct positive integers of $S$ on the same line.

Limits

• $1 \le T \le 10$
• $N$ is exactly $20$.
• Every element of $S$ is a positive integer smaller than $10^5$.
• No two elements of $S$ are equal.

For each test case, first print one line holding "Case #x:", where x is the case number starting from 1.

If two different subsets with the same sum exist, print them on the next two lines, one subset per line. On each line print the elements of that subset in increasing order, separated by single spaces. If no such pair exists, print "Impossible" on a single line.

Several pairs can satisfy the condition, so exactly one pair counts as correct. Write the elements of $S$ in increasing order as $s_1 < s_2 < \cdots < s_{20}$, and give a non-empty subset $A$ the code $\operatorname{code}(A) = \sum_{s_i \in A} 2^{i-1}$. Among all pairs of different subsets with the same sum, take the pair whose larger code is smallest; if several pairs remain, take the one whose smaller code is smallest. Print the subset with the smaller code first.