시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 3 3 75.000%

문제

남규는 어떤 성격 진단 테스트를 받게 되었다. 이 테스트는 선택지가 5개인 여러 개의 질문으로 이루어져 있으며, 각 질문은 5개의 활동 중에서 무엇을 제일 선호하는지를 반드시 하나만 고르도록 되어 있다.

당신은 오후 여가 시간에 무엇을 하시겠습니까?

(a) League of Legends
(b) The Binding of Isaac
(c) 옆에서 코딩하는 재혁이 괴롭히기
(d) 내일 시험이 있지만 시험공부 하지 않기
(e) 잠자기

각 활동들은 커다란 셋에서 무작위로 뽑혀졌다. 즉, "잠자기"라는 선택지가 여러 개의 질문에 걸쳐 등장할 수 있다.

남규가 선택한 답안은 다른 모든 답안보다 더 선호한다는 의미를 갖게 되며, 만약 남규가 A, B, C, D, E 중에서 A를 선택했다면, A는 B, C, D, E 각각에 대해 더 선호도를 갖고 있다는 뜻이다. 만약 어떤 질문에서 X가 Y보다 선호도가 높다는 것이 드러났고, 다른 어떤 질문에서 Y보다 Z가 선호도가 높다는 것이 드러났다면, X의 선호도는 Z보다도 높다는 사실을 도출해낼 수 있다.

그러나 남규는 테스트를 대충 치뤄서 모순적인 답안이 발생하게 되었다. 모순적인 답안은 어떤 X, Y에 대해서, X가 Y보다 선호도가 높다는 결과와 Y가 X보다 선호도가 높다는 결과가 동시에 존재하는 것을 의미한다. 이런 모순적인 답안이 발생하면 작성자는 인성파탄자로 검사된다. 그래서 남규는 테스트 한 번 잘못 쳤다고 졸지에 인성파탄자가 되고 말았다. 

여러 개의 테스트와 대답한 데이터가 주어졌을 때, 테스트에 등장한 모든 활동들을 분할(partition)하되, 각 그룹에서는 어떤 두 쌍을 골라도 두 활동 사이에 모순이 존재하도록 하시오.

입력

입력은 여러 개의 테스트 케이스로 주어지며, 입력의 끝에는 0이 주어진다.

각 테스트 케이스의 첫 번째 줄에는 질문의 개수 N이 주어진다. 이어서 N개의 각 줄에는 5개의 서로 다른 활동 이름이 주어지고, 그 옆에 작성자가 선택한 활동 이름이 주어진다. 작성자는 반드시 해당 줄에 존재하는 활동을 선택했으며, 모든 활동 이름은 영문 대문자 1글자이다.

출력

각 테스트 케이스마다 정답을 출력한다. 한 줄에 하나의 그룹(partition)을 알파벳순으로 출력하며, 각 그룹의 알파벳순으로 가장 앞에 오는 원소 기준으로 그룹들도 알파벳순으로 출력되어야 한다. 반드시 질문에 존재했던 활동들만을 출력해야 한다.

각 테스트 케이스의 사이에는 빈 줄을 하나 출력한다.

예제 입력

4
A B C D E C
F C H I J J
K B H I F I
K C E B J K
0

예제 출력

A
B
C
D
E
F
H
I J K

힌트