마술

최근에 당신은 마술 공연을 보러 갔다. 그중 한 마술이 매우 인상적이어서, 그 비밀을 밝혀내기로 했다!

마술사는 먼저 16장의 카드를 정사각형 격자에 배치한다. 카드가 놓인 행은 4개이고, 각 행에는 카드가 4장씩 있다. 각 카드의 보이는 면에는 1부터 16까지의 서로 다른 수가 하나씩 적혀 있다. 다음으로 마술사는 지원자에게 카드 한 장을 고르고 그 카드가 어느 행에 있는지 말해 달라고 한다.

마지막으로 마술사는 16장의 카드를 다시 정사각형 격자에 배치하며, 순서는 달라질 수도 있다. 마술사는 다시 한번 지원자에게 그녀의 카드가 어느 행에 있는지 묻는다. 마술사는 이 두 질문의 답만으로 지원자가 고른 카드를 정확히 알아낸다. 놀랍지 않은가?

당신은 마술사의 기법을 이해하는 데 도움이 되는 프로그램을 작성하기로 한다. 프로그램에는 카드의 두 가지 배치와 두 질문에 대한 지원자의 답, 즉 첫 번째 배치에서 선택한 카드가 있는 행 번호와 두 번째 배치에서 선택한 카드가 있는 행 번호가 주어진다. 행에는 위에서 아래로 1부터 4까지 번호가 매겨져 있다.

프로그램은 지원자가 어떤 카드를 골랐는지 판별해야 한다. 또는 지원자가 골랐을 가능성이 있는 카드가 하나보다 많거나(마술사가 제대로 하지 못한 경우), 지원자의 답과 일치하는 카드가 하나도 없는지(지원자가 속임수를 쓴 경우) 판별해야 한다.

이 문제 풀기

일반적으로 Google Code Jam 문제에는 1 작은 입력과 1 큰 입력이 있다. 이 문제에는 1 작은 입력만 있다. 작은 입력을 해결했다면 이 문제를 모두 해결한 것이다.

제한

시간 제한: 60초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ 두 답 모두 ≤ 4. 1부터 16까지의 각 수는 각각의 배치에 정확히 한 번씩 등장한다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 첫 번째 질문의 답인 정수 하나가 적힌 줄로 시작한다. 다음 4개 줄은 카드의 첫 번째 배치를 나타낸다. 각 줄에는 하나의 공백으로 구분된 4개의 정수가 있다. 다음 줄에는 두 번째 질문의 답이 주어지고, 이어지는 네 줄에는 같은 형식으로 두 번째 배치가 주어진다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작한다.

지원자가 고를 수 있었던 카드가 하나뿐이라면 y는 그 카드에 적힌 수여야 한다. 지원자가 고를 수 있었던 카드가 여러 장이라면 y는 따옴표 없이 "Bad magician!"여야 한다. 지원자의 답과 일치하는 카드가 없다면 y는 따옴표 없이 "Volunteer cheated!"여야 한다. 문자열은 정확해야 하므로 여기에서 복사하여 붙여 넣는 것을 고려하라.