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

문제

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

John Doe
W3sicHJvYmxlbV9pZCI6IjQ0MTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2MzhcdWM4ZmNcdWMyZGQgXHVkMjJjXHVkNDVjXHViYzk1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ2MzhcdWM4ZmNcdWMyZGQmbmJzcDtcdWQyMmNcdWQ0NWNcdWJjOTVcdWM3NDAgXHVjMTIwXHVkNjM4XHViM2M0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWQ2YzRcdWJjZjRcdWI0ZTRcdWM3NTggXHVjMjFjXHVjNzA0XHViOTdjIFx1YjllNFx1YWUzMFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Y2M5OFx1Yzc0Y1x1YzVkMFx1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4XHViODVjIFx1YzEyMFx1ZDBkZFx1YjQxYyZuYnNwO1x1ZDZjNFx1YmNmNFx1YjRlNFx1Yzc1OCBcdWQ0NWNcdWI5Y2MmbmJzcDtcdWMxMzhcdWFjZTAsIFx1YjljY1x1YzU3ZCBcdWQ1NWMgXHVkNmM0XHViY2Y0XHVhYzAwIFx1YzgwOFx1YmMxOFx1Yzc0NCBcdWIxMThcdWIyOTQoXHVjZDA4XHVhY2ZjKSZuYnNwO1x1ZDQ1Y1x1Yjk3YyBcdWM1YmJcdWM3M2NcdWJhNzQgXHVhZGY4IFx1ZDZjNFx1YmNmNFx1YWMwMCBcdWIyZjlcdWMxMjBcdWI0MWNcdWIyZTQuIFx1YzViNFx1YjI5MCBcdWQ2YzRcdWJjZjRcdWIzYzQgXHVjODA4XHViYzE4XHVjNzQ0IFx1YjExOFx1YjI5NCZuYnNwO1x1ZDQ1Y1x1Yjk3YyBcdWM1YmJcdWM5YzAgXHViYWJiXHVkNTU4XHViYTc0LCBcdWNjYWIgXHViYzg4XHVjOWY4XHViODVjIFx1YzEyMFx1ZDBkZFx1YjQxYyZuYnNwO1x1ZDQ1YyBcdWMyMThcdWFjMDAgXHVhYzAwXHVjN2E1IFx1YzgwMVx1Yzc0MCBcdWQ2YzRcdWJjZjRcdWI0ZTRcdWM3NDQmbmJzcDtcdWQwYzhcdWI3N2RcdWMyZGNcdWQwYThcdWIyZTQuJm5ic3A7XHVhZGY4XHViOWFjXHVhY2UwIFx1Yzc3NCAoXHVkMGM4XHViNzdkXHViNDFjIFx1ZDZjNFx1YmNmNFx1Yjk3YyBcdWNjYWIgXHViYzg4XHVjOWY4XHViODVjIFx1YzEyMFx1ZDBkZFx1ZDU1YylcdWQ0NWNcdWM1ZDBcdWMxMWMgXHVkMGM4XHViNzdkXHViNDFjIFx1ZDZjNFx1YmNmNFx1YjRlNFx1Yzc0NCBcdWM4MWNcdWM2NzhcdWQ1NWMgXHViMDk4XHViYTM4XHVjOWMwIFx1ZDZjNFx1YmNmNFx1YjRlNCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YjE5Mlx1Yzc0MCBcdWMxMjBcdWQ2MzhcdWIzYzRcdWI5N2MgXHVhYzAwXHVjOWM0Jm5ic3A7XHVkNmM0XHViY2Y0XHVjNWQwXHVhYzhjIFx1ZDQ1Y1x1Yjk3YyBcdWIzNTRcdWQ1NzRcdWM5MDBcdWIyZTQuIFx1Yzc3NCBcdWFjZmNcdWM4MTVcdWM3NDQgXHVkNTVjIFx1ZDZjNFx1YmNmNFx1YWMwMCBcdWM4MDhcdWJjMThcdWM3NzQgXHViMTE4XHViMjk0Jm5ic3A7XHVkNDVjXHViOTdjIFx1YzViYlx1YWM3MFx1YjA5OCwgXHViYWE4XHViNGUwIFx1ZDZjNFx1YmNmNFx1YWMwMCBcdWIzZDlcdWM4MTBcdWM3NzQgXHViNDIwIFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWJjMThcdWJjZjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YzlmOFx1YzkwNFx1Yzc0MCBuICZsdDs9IDIwXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWM4MTVcdWMyMThcdWM3NzRcdWFjZTAgXHVkNmM0XHViY2Y0XHVjNzkwXHViNGU0XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgblx1YWMxY1x1Yzc1OCBcdWM3ODVcdWI4MjVcdWM3NDAgXHVkNmM0XHViY2Y0XHVjNzkwXHViNGU0XHVjNzU4IFx1Yzc3NFx1Yjk4NFx1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWM3NzRcdWI5ODRcdWM3NDAgXHVjZDVjXHViMzAwIDgwXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwIFx1ZDQ1Y1x1ZDYwNFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWJiMzhcdWM3OTBcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTVjXHViMmU0LiBcdWNkNWNcdWIzMDAgMTAwMFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NzQgXHVjNzg1XHViODI1XHViNDE4XHViMjk0XHViMzcwLCBcdWFjMDFcdWFjMDFcdWM3NDAgXHVkMjJjXHVkNDVjIFx1YzZhOVx1YzljMFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXHVhYzAxIFx1YzkwNFx1YjljOFx1YjJlNCAxXHViZDgwXHVkMTMwIG5cdWFlNGNcdWM5YzBcdWM3NTggXHVjMjJiXHVjNzkwXHViOTdjIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4XHViODVjIFx1YzEyMFx1ZDYzOFx1ZDU1OFx1YjI5NCBcdWQ2YzRcdWJjZjRcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWNlMCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWIyOTQgXHViNDUwIFx1YmM4OFx1YzlmOFx1Yjg1YyBcdWMxMjBcdWQ2MzhcdWQ1NThcdWIyOTQgXHVkNmM0XHViY2Y0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWFjZTAgXHViMDk4XHViYTM4XHVjOWMwXHViM2M0IFx1YWRmOFx1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFx1YjJmOVx1YzEyMFx1YjQxYyBcdWQ2YzRcdWJjZjRcdWM3NTggXHVjNzc0XHViOTg0IFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YWM3MFx1YjA5OCwmbmJzcDtcdWIzZDlcdWM4MTBcdWM3OTBcdWI0ZTRcdWM3NTggXHVjNzc0XHViOTg0Jm5ic3A7XHVjNWVjXHViN2VjIFx1YzkwNFx1Yzc3NCBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0NDE5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQXVzdHJhbGlhbiBWb3RpbmciLCJkZXNjcmlwdGlvbiI6IjxwPkF1c3RyYWxpYW4gYmFsbG90cyByZXF1aXJlIHRoYXQgdGhlIHZvdGVyIHJhbmsgdGhlIGNhbmRpZGF0ZXMgaW4gb3JkZXIgb2YgY2hvaWNlLiBJbml0aWFsbHkgb25seSB0aGUgZmlyc3QgY2hvaWNlcyBhcmUgY291bnRlZCBhbmQgaWYgb25lIGNhbmRpZGF0ZSByZWNlaXZlcyBtb3JlIHRoYW4gNTAlIG9mIHRoZSB2b3RlLCB0aGF0IGNhbmRpZGF0ZSBpcyBlbGVjdGVkLiBJZiBubyBjYW5kaWRhdGUgcmVjZWl2ZXMgbW9yZSB0aGFuIDUwJSwgYWxsIGNhbmRpZGF0ZXMgdGllZCBmb3IgdGhlIGxvd2VzdCBudW1iZXIgb2Ygdm90ZXMgYXJlIGVsaW1pbmF0ZWQuIEJhbGxvdHMgcmFua2luZyB0aGVzZSBjYW5kaWRhdGVzIGZpcnN0IGFyZSByZWNvdW50ZWQgaW4gZmF2b3VyIG9mIHRoZWlyIGhpZ2hlc3QgcmFua2VkIGNhbmRpZGF0ZSB3aG8gaGFzIG5vdCBiZWVuIGVsaW1pbmF0ZWQuIFRoaXMgcHJvY2VzcyBjb250aW51ZXMgW3RoYXQgaXMsIHRoZSBsb3dlc3QgY2FuZGlkYXRlIGlzIGVsaW1pbmF0ZWQgYW5kIGVhY2ggYmFsbG90IGlzIGNvdW50ZWQgaW4gZmF2b3VyIG9mIGl0cyByYW5rZWQgbm9uLWVsaW1pbmF0ZWQgY2FuZGlkYXRlXSB1bnRpbCBvbmUgY2FuZGlkYXRlIHJlY2VpdmVzIG1vcmUgdGhhbiA1MCUgb2YgdGhlIHZvdGUgb3IgdW50aWwgYWxsIGNhbmRpZGF0ZXMgYXJlIHRpZWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBpcyBhbiBpbnRlZ2VyIG4gJmx0Oz0gMjAgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIGNhbmRpZGF0ZXMuIFRoZSBuZXh0IG4gbGluZXMgY29uc2lzdCBvZiB0aGUgbmFtZXMgb2YgdGhlIGNhbmRpZGF0ZXMgaW4gb3JkZXIuIE5hbWVzIG1heSBiZSB1cCB0byA4MCBjaGFyYWN0ZXJzIGluIGxlbmd0aCBhbmQgbWF5IGNvbnRhaW4gYW55IHByaW50YWJsZSBjaGFyYWN0ZXJzLiBVcCB0byAxMDAwIGxpbmVzIGZvbGxvdzsgZWFjaCBjb250YWlucyB0aGUgY29udGVudHMgb2YgYSBiYWxsb3QuIFRoYXQgaXMsIGVhY2ggY29udGFpbnMgdGhlIG51bWJlcnMgZnJvbSAxIHRvIG4gaW4gc29tZSBvcmRlci4gVGhlIGZpcnN0IG51bWJlciBpbmRpY2F0ZXMgdGhlIGNhbmRpZGF0ZSBvZiBmaXJzdCBjaG9pY2U7IHRoZSBzZWNvbmQgbnVtYmVyIGluZGljYXRlcyBjYW5kaWRhdGUgb2Ygc2Vjb25kIGNob2ljZSwgYW5kIHNvIG9uLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBPdXRwdXQgY29uc2lzdHMgb2YgZWl0aGVyIGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgbmFtZSBvZiB0aGUgd2lubmVyIG9yIHNldmVyYWwgbGluZXMgY29udGFpbmluZyB0aGUgbmFtZXMgb2YgdGhlIGNhbmRpZGF0ZXMgd2hvIHRpZWQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d