Australian Voting

호주식 투표 제도에서는 투표권자가 모든 후보에 대해 선호도 순으로 순위를 매긴다. 처음에는 1순위로 선택한 것만 집계하며 한 후보가 50%이상 득표하면 그 후보가 바로 선출된다. 하지만 50%이상 득표한 후보가 없으면 가장 적은 표를 받은 후보(둘 이상이 될 수도 있음)가 우선 탈락된다. 그리고 이렇게 탈락된 후보를 1순위로 찍었던 표만 다시 집계하여 아직 탈락되지 않은 후보들 가운데 가장 높은 선호도를 얻은 후보가 그 표를 얻는다. 이런 식으로 가장 약한 후보들을 탈락시키면서 그 다음 순위의 아직 탈락하지 않은 후보에게 표를 주는 과정을 50%이상의 표를 얻는 후보가 나오거나 탈락되지 않은 모든 후보가 동률이 될 때까지 반복한다.

입력 케이스의 개수를 나타내는 양의 정수 한 개가 들어있는 행으로 시작되며 그 줄에는 그 숫자밖에 입력되지 않는다. 그 뒤에는 빈 줄이 하나 들어가고 서로 다른 입력 케이스 사이에는 두 개의 빈 줄이 입력된다. 각 케이스의 첫번째 줄에는 후보 수를 나타내는 20 이하의 정수 n이 입력된다. 그 밑으로 n개의 줄에 걸쳐서 후보의 이름이 순서대로 입력되며 각 후보의 이름은 80글자 이하로, 출력 가능한 문자로 구성된다. 그 뒤에는 최대 1,000줄이 입력될 수 있는데, 각 줄에는 투표 내역이 입력된다. 각 투표 내역에는 어떤 순서로 1부터 n까지의 수가 입력된다. 첫번째 숫자는 1순위로 찍은 후보의 번호, 두번째 숫자는 2순위로 찍은 후보의 번호, 이런 식으로 숫자가 기록된다.

각 테스트 케이스에 대해 당선된 후보의 이름 한 줄, 또는 동률을 이룬 후보들의 이름이 들어있는 여러 줄을 출력한다. 두 개 이상의 테스트 케이스가 있는 경우 각 결과는 빈 줄로 구분한다.

~cpp 
1
 
3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

~cpp 
John Doe

문제분류 AOI