클루

보드게임 클루(Clue) 를 아시나요? 논리적 단서를 조합해 살인 사건의 장소, 흉기, 범인 을 알아내는 게임입니다. 후보는 다음과 같습니다.

• 장소(Location): Ballroom, Billiard Room, Conservatory, Dining Room, Hall, Kitchen, Library, Lounge, Study
• 흉기(Weapon): Candlestick, Gun, Knife, Lead Pipe, Rope, Wrench
• 범인(Murderer): Colonel Mustard, Miss Scarlet, Reverend Green, Mrs. Peacock, Mrs. White, Professor Plum

각 장소, 흉기, 범인은 한 장의 카드로 만들어집니다. 세 종류에서 각각 한 장씩(장소 1장, 흉기 1장, 범인 1장)이 숨겨지며, 이 숨겨진 세 장이 바로 우리가 알아내야 하는 정답입니다. 나머지 카드는 모두 $n$ 명의 플레이어에게 남김없이 나누어집니다.

플레이어는 차례대로 질의를 합니다. 하나의 질의는 장소 하나, 흉기 하나, 범인 하나로 이루어집니다. 플레이어 $i$ 가 질의를 하면, 플레이어 $i+1, i+2, \dots, n, 1, \dots, i-1$ 이 이 순서대로, 질의에 포함된 세 장의 카드 중 하나를 플레이어 $i$ 에게 보여 주어 질의를 반박하려 시도합니다.

• 어떤 플레이어가 세 장 중 최소 한 장을 가지고 있다면, 반드시 그중 한 장을 보여 주어야 합니다. 단, 여러 장을 가지고 있다면 어느 것을 보여 줄지는 자유롭게 고를 수 있습니다.
• 세 장 중 아무것도 가지고 있지 않다면 보여 줄 수 없으며, 없다고 답합니다.

한 플레이어가 카드를 보여 주는 순간 그 질의는 즉시 종료되고, 그 뒤 순번의 플레이어에게는 묻지 않습니다. 이렇게 플레이어들은 누가 어떤 카드를 가지고 있는지를 점점 알아내고, 결국 숨겨진 세 장을 추론합니다.

질의와 그 응답으로부터 후보에 대해 알아낼 수 있는 것을 최대한 알아내는 프로그램을 작성해야 합니다. 여러분은 플레이어 1 이며, 자신이 낸 질의로부터만 정보를 얻는다고 가정합니다. 따라서 입력에는 여러분 자신의 질의와 그에 대한 응답만 주어지고, 다른 플레이어의 질의는 절대 주어지지 않습니다. (실제 게임에서는 질의를 하려면 주사위를 굴려 이동해야 하고 다른 플레이어의 질의에서 제시된 카드도 볼 수 있지만, 문제를 단순하게 하기 위해 두 가지 모두 무시합니다.)

모든 카드 이름은 위 목록에 적힌 것과 대소문자까지 완전히 똑같이 표기됩니다.

첫 번째 줄에 데이터 집합의 개수 $K$ 가 주어집니다. 이어서 $K$ 개의 데이터 집합이 다음 형식으로 주어집니다.

각 데이터 집합의 첫 줄에는 세 정수 $n, c, q$ 가 주어지며, 각각 플레이어 수, 여러분이 받은 카드 수, 질의 수를 뜻합니다. ($2 \le n \le 6$, $0 \le c \le 18$, $0 \le q \le 1000$)

그다음 $c$ 개의 줄에 여러분이 가진 카드의 이름이 한 줄에 하나씩 주어집니다.

이어서 $q$ 개의 질의가 주어집니다. 각 질의는 다음 형식입니다. 첫 줄에 제안된 장소, 둘째 줄에 흉기, 셋째 줄에 범인이 주어집니다. 그다음에는 다른 플레이어들의 응답이 최대 $n-1$ 줄 주어집니다. 각 응답은 (해당 플레이어가 세 카드 중 아무것도 없으면) 단어 Nothing 이거나, 그렇지 않으면 그 플레이어가 보여 준 카드의 이름입니다. 응답이 카드 이름이면 그 질의는 거기서 끝나고, 다음 줄부터 새로운 질의가 시작됩니다.

모든 카드 이름(가진 카드, 질의의 카드, 응답의 카드)은 위 목록과 대소문자까지 똑같이 표기됩니다.

각 데이터 집합마다 먼저 Data Set x: 를 한 줄에 출력합니다. 여기서 $x$ 는 데이터 집합의 번호입니다. 이어지는 줄에는 아직 배제되지 않은(즉, 여전히 숨겨진 카드일 가능성이 있는) 장소, 흉기, 범인을 차례로 한 줄에 하나씩 출력합니다. 세 종류를 이 순서(장소 → 흉기 → 범인)로 출력하며, 각 종류 안에서는 이름을 알파벳 순으로 정렬합니다.

연속한 데이터 집합 사이는 빈 줄 하나로 구분합니다.