Voting in Australia is kind of an interesting matter. Instead of simply choosing your favorite candidate, you actually rank everyone in order of decreasing awesomeness. Initially, only the first choices are counted (that is, those candidates which people found most awesome). If one of the candidates receives more than fifty percent of the votes, (s)he wins the election. Otherwise, all candidates tied for the lowest number of votes are eliminated (not literally). Ballots that ranked those candidates as most awesome are recounted in favor of their highest-ranked candidate still alive (not literally). This process continues until one candidate wins or until all remaining candidates are tied.

This system is so complicated that it is now your job to implement it!


The input begins with a single positive integer on a line by itself indicating the number of cases following, each as described below. This line is followed by a blank line. There is also a blank line between two consecutive inputs.

The first line of each case is an integer \(n \leq 20\) indicating the number of candidates. The next \(n\) lines consist of the names of the candidates in order, each up to 80 characters in length and containing any printable characters. Up to 1000 lines follow, each containing the contents of a ballot. Each ballot contains the numbers from 1 to \(n\) in some order. The first number indicates the most awesome candidate; the second number indicates the second most awesome candidate, and so on.


The output of each test case consists of either a single line containing the name of the winner or several lines containing the names of all candidates who are tied. The output of each two consecutive cases are separated by a blank line.

Sample Input


Boilerdang Chickenstrips
Rumblesack Snugglesnatch
Blubberbutt Cabbagepatch
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

Sample Output

Boilerdang Chickenstrips

This is challenge 10142 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

Upload Solution

Please log in to submit your solution.


Difficulty (5 votes)
Average test runtime 0.35
Points (changes over time) 10
Tried by 10 users
Solved by 7 users

Global ranking

# Name Runtime Points worth
1 贝尔恩德 0.13 19
2 ,s/java/NaN/gi 0.14 17
3 Chris Danger 0.22 11
4 JB 0.25 10
5 Dark 0.47 5
6 Skøgland 0.52 5
7 KnorpelSenf 0.71 3