题目描述

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}$.)

5
8
0 1 2 3 4 5 6 7
1 1 1 1 1 1 1 1
4
0 1 2 3
1 3 3 1
4
0 1 3 4
4 4 4 4
3
-1 0 1
1 2 1
5
-2 -1 0 1 2
1 2 2 2 1

Case #1: 1 2 4
Case #2: 1 1 1
Case #3: 0 0 1 3
Case #4: -1 1
Case #5: -2 1 1

提示

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<-1$. So $-1\ -1\ 2$ would not be an acceptable answer. $1\ -2\ 1$ would also be unacceptable, even though it is the correct set, because the elements are not listed in nondecreasing order.

Limits

• $1 \leq \mathrm{T} \leq 100 .$
• $1 \leq \mathrm{P} \leq 10000 .$
• $\mathrm{F}_{\mathrm{i}} \geq 1$.

Small dataset

• Time limit: 240 5 seconds.
• $\mathrm{S}$ will contain between 1 and 20 elements.
• $0 \leq$ each $\mathrm{E}_{\mathrm{i}} \leq 10^{8}$.

Large dataset

• Time limit: 480 10 seconds.
• $\mathrm{S}$ will contain between 1 and 60 elements.
• $-10^{10} \leq$ each $\mathrm{E}_{\mathrm{i}} \leq 10^{10}$.