로그 집합

집합 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가 여러 개라면, 원래 집합 S는 그 가능한 집합 중 가장 앞선 집합임이 보장된다. 같은 길이의 집합 $S_{1}$이 다른 집합 $S_{2}$보다 앞서는지 판단하려면, 각 집합을 비내림차순으로 정렬한 다음 두 집합이 다른 가장 왼쪽 위치를 살펴본다. 그 위치에서 $S_{1}$의 원소가 $S_{2}$의 원소보다 작을 때, 그리고 그럴 때에만 $S_{1}$이 더 앞선다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ P ≤ 10000. $F_{i}$ ≥ 1.

작은 데이터 세트

시간 제한: 240초. S에는 1개 이상 20개 이하의 원소가 포함된다. 0 ≤ 각 $E_{i}$ ≤ $10^{8}$.

큰 데이터 세트

시간 제한: 480초. S에는 1개 이상 60개 이하의 원소가 포함된다. -$10^{10}$ ≤ 각 $E_{i}$ ≤ $10^{10}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 P가 있는 한 줄과, 각각 공백으로 구분된 P개의 정수가 있는 두 줄로 구성된다. 그중 첫 번째 줄에는 S'에 나타나는 서로 다른 모든 원소 $E_{1}$, $E_{2}$, ..., $E_{P}$가 오름차순으로 주어진다. 두 번째 줄에는 각 값이 S'에 나타나는 횟수 $F_{1}$, $F_{2}$, ..., $F_{P}$가 주어진다. 즉, 임의의 i에 대해 원소 $E_{i}$는 S'에 $F_{i}$번 나타난다.

각 테스트 케이스마다 "Case #x: "를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이며, 그 뒤에 원래 집합 S의 원소를 공백으로 구분하여 비내림차순으로 출력한다. (S의 원소를 직접 나열해야 하며, S'에 대해 하는 것처럼 원소 목록과 빈도 목록을 따로 제공해서는 안 된다.)

케이스 #4과 #5은 작은 데이터 세트의 제한에 속하지 않음에 유의하라.

케이스 #4에서 S = {-1, 1}는 조건을 만족하는 유일한 집합이다. (그 부분집합은 {}, {-1}, {1}, {-1, 1}이다. 각각의 합은 0, -1, 1, 0이므로 S'에는 -1가 하나, 0이 둘, 1가 하나 있으며, 이는 입력에 명시된 내용과 일치한다.)

케이스 #5에서는 S = {-1, -1, 2}도 같은 S' = {-2, -1, -1, 0, 0, 1, 1, 2}을 만든다는 점에 유의하라. 하지만 처음으로 다른 위치에서 -2 < -1이므로 S = {-2, 1, 1}가 {-1, -1, 2}보다 앞선다. 따라서 -1 -1 2은 허용되는 답이 아니다. 1 -2 1도 올바른 집합이기는 하지만 원소가 비내림차순으로 나열되지 않았으므로 허용되지 않는다.