로그 집합 (라지)

집합 S의 멱집합은 S의 모든 부분집합을 모은 집합이다. 공집합과 S 자신도 포함한다. 집합에서 멱집합을 만드는 일은 쉽지만, 이 문제는 반대 방향으로 간다.

정수로 이루어진 집합 S가 있다. 원소가 서로 다를 필요는 없다. S의 멱집합을 구한 다음, 멱집합의 각 원소, 즉 각 부분집합을 그 부분집합의 원소 합으로 바꾸어 새로운 집합 S'을 만들었다. 예를 들어 S = {-1, 1}이면 S의 멱집합은 {{}, {-1}, {1}, {-1, 1}}이므로 S' = {0, -1, 1, 0}이다. S'에는 같은 값이 여러 번 들어갈 수 있으므로, S의 원소가 N개면 S'의 원소는 항상 정확히 $2^N$개다.

S'에 나타나는 값과 각 값의 등장 횟수가 주어진다. 원래 집합 S를 복원하라. S는 반드시 존재한다. 같은 S'을 만드는 S가 여럿이면 원래 집합은 그중 가장 앞서는 것이다. 원소 개수가 같은 두 집합 S1과 S2 중 어느 쪽이 앞서는지는 이렇게 정한다. 각 집합을 비내림차순으로 정렬한 뒤 두 집합이 처음으로 달라지는 위치를 찾는다. 그 위치의 값이 더 작은 쪽이 앞선다.

첫 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다. 첫 줄에는 정수 P가 주어진다. 둘째 줄에는 S'에 나타나는 서로 다른 값 $E_1, E_2, \dots, E_P$가 오름차순으로 주어진다. 셋째 줄에는 각 값의 등장 횟수 $F_1, F_2, \dots, F_P$가 주어진다. 즉 값 $E_i$는 S'에 $F_i$번 나타난다.

제한

• $1 \le T \le 100$
• $1 \le P \le 10000$
• $F_i \ge 1$
• S의 원소 개수는 1개 이상 60개 이하다.
• $-10^{10} \le E_i \le 10^{10}$
• $F_1 + F_2 + \dots + F_P = 2^N$이다. 여기서 N은 S의 원소 개수다.

각 테스트 케이스마다 한 줄에 "Case #x: "를 출력하고, 그 뒤에 원래 집합 S의 원소를 비내림차순으로 공백 하나씩 두고 출력한다. x는 1부터 시작하는 테스트 케이스 번호다. S'처럼 값과 횟수를 두 줄로 나누지 말고 S의 원소를 그대로 나열한다.

S'만으로 S가 하나로 정해지지 않을 때가 있다. 예를 들어 {-2, 1, 1}과 {2, -1, -1}은 같은 S'을 만든다. 이때 답은 더 앞서는 {-2, 1, 1}이다.