인수 전쟁

시간 제한1초메모리 제한128 MB

문제

두 대기업 Takeover Incorporated와 Buyout Limited가 인수 전쟁을 벌이고 있습니다. 각 기업은 여러 개의 자회사를 거느리며, 모든 자회사에는 정해진 시장 가치가 있습니다. 이 전쟁의 목표는 상대 기업을 시장에서 완전히 몰아내는 것입니다.

각 기업은 자신의 차례에 인수를 정확히 한 번 수행하며, 인수는 우호적 인수 또는 적대적 인수 중 하나입니다.

  • 우호적 인수. 같은 기업에 속한 자회사 두 개를 하나로 합칩니다. 합쳐진 자회사의 시장 가치는 두 자회사 가치의 합이며, 두 자회사의 크기에는 아무런 제약이 없습니다.
  • 적대적 인수. 한 기업의 자회사 $A$가 상대 기업의 자회사 $B$를 흡수합니다. 이는 $A$의 시장 가치가 $B$의 시장 가치보다 엄격히 클 때에만 가능합니다. 인수가 성사되면 $B$는 시장에서 사라지고, $A$의 가치는 변하지 않습니다($B$의 자산을 흡수해 얻는 이득이 인수 비용과 정확히 상쇄되기 때문입니다).

시장 가치는, 전쟁이 어떻게 전개되더라도 서로 다른 기업에 속한 두 자회사의 시장 가치가 결코 같아지지 않도록 주어진다고 가정해도 됩니다.

두 기업은 번갈아 수를 두며 Takeover Incorporated가 먼저 시작합니다. 각 기업은 자신의 차례에 가능한 인수가 있으면 반드시 인수를 해야 하고, 가능한 인수가 하나도 없을 때에만(즉, 자회사가 하나뿐이고 그 자회사가 상대의 어떤 자회사도 흡수할 수 없을 때) 아무것도 하지 않습니다. 어떤 기업의 자회사가 모두 인수당하는 순간 그 기업은 전쟁에서 패배합니다.

두 기업이 모두 최적으로 행동할 때 어느 기업이 반드시 승리하는지 구하세요.

이해를 돕기 위해 첫 번째 예제를 살펴봅시다. Takeover Incorporated는 가치 $7, 1, 1$의 자회사를, Buyout Limited는 가치 $5$짜리 자회사 두 개를 가집니다. Takeover는 가치 $7$인 자회사로 상대의 가치 $5$ 자회사 하나를 흡수하고, 이후 가치 $1$인 자회사 하나를 적대적 인수로 잃더라도 남은 가치 $5$ 자회사마저 흡수해 승리합니다. 두 번째 예제에서 Takeover는 $3, 3, 3, 3$을, Buyout은 $5, 5$를 가집니다. Takeover에는 $5$보다 큰 자회사가 없어 우호적 인수만 반복할 수밖에 없는데, Buyout은 두 자회사를 합쳐 가치 $10$을 만들 수 있으므로 결국 Buyout이 승리합니다.

입력

입력은 여러 개의 테스트 케이스로 이루어지며 파일의 끝에서 종료됩니다. 각 테스트 케이스는 세 줄로 주어집니다.

  • 첫째 줄에는 두 정수 $N$과 $M$이 주어집니다($1 \le N, M \le 10^5$). 각각 Takeover Incorporated와 Buyout Limited의 자회사 수입니다.
  • 둘째 줄에는 Takeover Incorporated의 자회사 $N$개의 시장 가치 $a_i$가 주어집니다($1 \le a_i \le 10^{12}$).
  • 셋째 줄에는 Buyout Limited의 자회사 $M$개의 시장 가치 $b_j$가 주어집니다($1 \le b_j \le 10^{12}$).

출력

각 테스트 케이스마다 한 줄에 Case k: X 형식으로 출력합니다. 여기서 $k$는 $1$부터 시작하는 테스트 케이스 번호이고, $X$는 두 기업이 최적으로 행동할 때 전쟁에서 승리하는 기업으로 Takeover Incorporated 또는 Buyout Limited 중 하나입니다.