P13320 [GCJ 2012 #1B] Equal Sums

I have a set of positive integers $\mathbf{S}$. Can you find two non-empty, distinct subsets with the same sum? Note: A subset is a set that contains only elements from $\mathbf{S}$, and two subsets are distinct if they do not have exactly the same elements.

he first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow, one per line. Each test case begins with $\mathbf{N}$, the number of positive integers in $\mathbf{S}$. It is followed by $\mathbf{N}$ distinct positive integers, all on the same line.

For each test case, first output one line containing "Case #x:", where $\mathbf{x}$ is the case number (starting from 1). * If there are two different subsets of $\mathbf{S}$ that have the same sum, then output these subsets, one per line. Each line should contain the numbers in one subset, separated by spaces. * If it is impossible, then you should output the string "Impossible" on a single line. If there are multiple ways of choosing two subsets with the same sum, any choice is acceptable.

**Limits** - No two numbers in $\mathbf{S}$ will be equal. - $1 \leq \mathbf{T} \leq 10$. **Test set 1 (6 Pts, Visible Verdict)** - Time limit: ~~60~~ 12 seconds. - $\mathbf{N}$ is exactly equal to $20$. - Each number in $\mathbf{S}$ will be a positive integer less than $10^5$. **Test set 2 (37 Pts, Hidden Verdict)** - Time limit: ~~120~~ 30 seconds. - $\mathbf{N}$ is exactly equal to $500$. - Each number in $\mathbf{S}$ will be a positive integer less than $10^{12}$.