The *power set* of a set S is the set of all subsets of S
(including the empty set and 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 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 S'. For example, if S
= {-1, 1}, then the power set of S is {{}, {-1}, {1}, {-1, 1}}, and so
S' = {0, -1, 1, 0}. S' is allowed to contain duplicates, so if S has N
elements, then S' always has exactly 2^{N} elements.

Given a description of the elements in S' and their frequencies, can you
determine our original S? It is guaranteed that S exists. If there are
multiple possible sets S that could have produced S', we guarantee that
our original set S was the *earliest* one of those possibilities. To determine whether a set S_{1} is earlier than a different set S_{2} of the same length, sort each set into nondecreasing order and then examine the leftmost position at which the sets differ. S_{1} is earlier iff the element at that position in S_{1} is smaller than the element at that position in S_{2}.

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

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

1 ≤ **T** ≤ 100.

1 ≤ **P** ≤ 10000.

**F _{i}** ≥ 1.

S will contain between 1 and 20 elements.

0 ≤ each E_{i} ≤ 10^{8}.

S will contain between 1 and 60 elements.

-10^{10} ≤ each E_{i} ≤ 10^{10}.

Input |
Output |

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 |

In Case #4, 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 S' 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 S = {-1, -1, 2} also produces the same S' = {-2, -1, -1, 0, 0, 1, 1, 2}, but S = {-2, 1, 1} is earlier than {-1, -1, 2}, since at the first point of difference, -2 < -1. So

`-1 -1 2`

would `1 -2 1`

would also be unacceptable, even though it is the correct set, because the elements are not listed in nondecreasing order.
Points | Correct | Attempted |
---|---|---|

6pt | 197 | 212 |

19pt | 55 | 109 |