Log Set (Large)

Time limit5sMemory limit512 MB

Summary

Recover the original integer multiset from the frequency table of all its subset sums, breaking ties by lexicographic order.

Level: Hard8 of 10
Topics: Greedy, Sorting, Hash map
Solved: No attempts yet

Problem

The power set of a set S is the set of all subsets of S, including the empty set and S itself. Going from a set to its power set is easy. This problem goes the other way.

We started with a set S of integers, which do not have to be distinct. We took its power set, then replaced every member of the power set, that is every subset, with the sum of the elements of that subset, which gave a new set S'. For example, if S = {-1, 1}, then the power set of S is {{}, {-1}, {1}, {-1, 1}}, so S' = {0, -1, 1, 0}. S' may contain repeated values, so if S has N elements, then S' always has exactly $2^N$ elements.

You are given the values that appear in S' and how many times each one appears. Recover the original set S. S is guaranteed to exist. If several sets S produce the same S', the original set is the earliest of them. To decide which of two sets S1 and S2 with the same number of elements is earlier, sort each one into nondecreasing order and find the leftmost position where they differ. The set with the smaller value at that position is earlier.

Input

The first line has the number of test cases T. T test cases follow. Each test case has three lines. The first line has one integer P. The second line has the P distinct values $E_1, E_2, \dots, E_P$ that appear in S', in ascending order. The third line has the counts $F_1, F_2, \dots, F_P$ . That is, the value $E_i$ appears $F_i$ times in S'.

Limits

$1 \le T \le 100$
$1 \le P \le 10000$
$F_i \ge 1$
S has between 1 and 60 elements.
$-10^{10} \le E_i \le 10^{10}$
$F_1 + F_2 + \dots + F_P = 2^N$ , where N is the number of elements of S.

Output

For each test case, print one line containing "Case #x: " followed by the elements of the original set S in nondecreasing order, separated by single spaces. Here x is the test case number, starting from 1. List the elements of S directly instead of splitting them into a value line and a count line the way S' is given.

Notes

S' does not always pin down S. For example, {-2, 1, 1} and {2, -1, -1} produce the same S'. In that case the answer is the earlier one, {-2, 1, 1}.

Examples1

Example 1

Input

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

Expected output

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