P13231 [GCJ 2015 #3] Log Set

The power set of a set $\mathrm{S}$ is the set of all subsets of $\mathrm{S}$ (including the empty set and $\mathrm{S}$ itself). It's easy to go from a set to a power set, but in this problem, we'll go in the other direction! We've started with a set of (not necessarily unique) integers $\mathrm{S}$, found its power set, and then replaced every element in the power set with the sum of elements of that element, forming a new set $\mathrm{S}^{\prime}$. For example, if $\mathrm{S}=\{-1,1\}$, then the power set of $\mathrm{S}$ is $\{\{\},\{-1\},\{1\},\{-1,1\}\}$, and so $\mathrm{S}^{\prime}=\{0,-1,1,0\}$. $\mathrm{S}^{\prime}$ is allowed to contain duplicates, so if $\mathrm{S}$ has $\mathrm{N}$ elements, then $\mathrm{S}^{\prime}$ always has exactly $2^{\mathrm{N}}$ elements. Given a description of the elements in $\mathrm{S}^{\prime}$ and their frequencies, can you determine our original $\mathrm{S}$ ? It is guaranteed that $\mathrm{S}$ exists. If there are multiple possible sets $\mathrm{S}$ that could have produced $\mathrm{S}^{\prime}$, we guarantee that our original set $\mathrm{S}$ was the earliest one of those possibilities. To determine whether a set $\mathrm{S}_{1}$ is earlier than a different set $\mathrm{S}_{2}$ of the same length, sort each set into nondecreasing order and then examine the leftmost position at which the sets differ. $\mathrm{S}_{1}$ is earlier iff the element at that position in $\mathrm{S}_{1}$ is smaller than the element at that position in $\mathrm{S}_{2}$.

The first line of the input gives the number of test cases, $\mathrm{T}$. $\mathrm{T}$ test cases follow. Each consists of one line with an integer $\mathrm{P}$, followed by two more lines, each of which has $\mathrm{P}$ space-separated integers. The first of those lines will have all of the different elements $\mathrm{E}_{1}, \mathrm{E}_{2}, \ldots, \mathrm{E}_{\mathrm{P}}$ that appear in $\mathrm{S}^{\prime}$, sorted in ascending order. The second of those lines will have the number of times $\mathrm{F}_{1}, \mathrm{~F}_{2}, \ldots, \mathrm{F}_{\mathrm{P}}$ that each of those values appears in $\mathrm{S}^{\prime}$. That is, for any $\mathrm{i}$, the element $\mathrm{E}_{\mathrm{i}}$ appears $\mathrm{F}_{\mathrm{i}}$ times in $\mathrm{S}^{\prime}$.

For each test case, output one line containing "Case #x: ", where $\mathrm{x}$ is the test case number (starting from 1), followed by the elements of our original set $\mathrm{S}$, separated by spaces, in nondecreasing order. (You will be listing the elements of $\mathrm{S}$ directly, and not providing two lists of elements and frequencies as we do for $\mathrm{S}^{\prime}$.)

**Sample Explanation** Note that Cases #4 and #5 are not within the limits for the Small dataset. In Case #4, $\mathrm{S}=\{-1,1\}$ is the only possible set that satisfies the conditions. (Its subsets are $\{\},\{-1\},\{1\}$, and $\{-1,1\}$. Those have sums $0, -1, 1$, and $0$, respectively, so $\mathrm{S}^{\prime}$ has one copy of $-1$, two copies of $0$, and one copy of $1$, which matches the specifications in the input.) For Case #5, note that $\mathrm{S}=\{-1,-1,2\}$ also produces the same $\mathrm{S}^{\prime}=\{-2,-1,-1,0,0,1,1,2\}$, but $\mathrm{S}=\{-2,1,1\}$ is earlier than $\{-1,-1,2\}$, since at the first point of difference, $-2