4419번 - 호주식 투표법

호주식 투표법은 선호도 순서대로 후보들의 순위를 매기는 것이다. 처음에는 첫 번째로 선택된 후보들의 표만 세고, 만약 한 후보가 절반을 넘는(초과) 표를 얻으면 그 후보가 당선된다. 어느 후보도 절반을 넘는 표를 얻지 못하면, 첫 번째로 선택된 표 수가 가장 적은 후보들을 탈락시킨다. 그리고 이 (탈락된 후보를 첫 번째로 선택한)표에서 탈락된 후보들을 제외한 나머지 후보들 중 가장 높은 선호도를 가진 후보에게 표를 더해준다. 이 과정을 한 후보가 절반이 넘는 표를 얻거나, 모든 후보가 동점이 될 때까지 반복한다.

입력의 첫 째줄은 n <= 20을 만족하는 정수이고 후보자들의 수를 나타낸다. 그 다음 n개의 입력은 후보자들의 이름을 순서대로 나타낸다. 이름은 최대 80개의 문자로 이루어져 있고 표현될 수 있는 모든 문자를 포함한다. 최대 1000개의 줄이 입력되는데, 각각은 투표 용지를 의미한다. 즉, 각 줄마다 1부터 n까지의 숫자를 순서대로 가지고 있다. 첫 번째 숫자는 첫 번째로 선호하는 후보의 번호를 나타내고, 두 번째 숫자는 두 번째로 선호하는 후보의 번호를 나타내고 나머지도 그와 같다.

출력은 당선된 후보의 이름 하나이거나, 동점자들의 이름 여러 줄이 될 수 있다.