G :: Electing SSC Chair

Time Limit: 3 Seconds    Memory Limit: 65536 KB

Student Scientific Committee (SSC) has several members. In their first meeting, the SSC Chair is elected by the following rule. Every member votes and gives an ordered list of other members (including him/herself) who are candidate to be SSC chair. An election subcommittee (ES) will announce the winner (if there exists any) following this procedure which may be repeated in several rounds.
In the first round, ES will consider only the first choices in each member’s vote list. If a candidate gets more than half of the votes, he/she wins the election. Otherwise, the candidate with the lowest vote counts (or candidates, in the case of a tie for fewest votes) is eliminated from all vote lists and the procedure is repeated. This is continued until a winner is found, or ES realizes there is no winner. Note in each round empty vote lists are non-viable and if a candidate is the first choice in more than half of viable vote list, the candidate is winner.

Input

There are  multiple test cases in the input.  For each test case, first the number of candidates and the number of voter (all SSC members) are given respectively in one line separated with spaces (both values are at most 1000).  Next vote lists are coming; a line for the vote list of each member. For each vote list, the names of the candidates are listed in the order of preference. A candidate may not appear in a voted list. A candidate name is an alphanumeric (case-sensitive) string with no space in middle. No candidate is repeated on a single vote. The input terminate with “0 0”.

Output

For each test case, output a single line containing the name of the winner as it is in the input. If no one wins, print “There is no winner”.

Sample Input

3 8
Saeed Ali
Saeed Ali
Saeed Ali
Mohammad Ali
Mohammad Ali
Mohammad Ali
Ali Saeed
Ali Saeed
2 2
Ali Reza
Reza Ali
0 0

Sample Output

Saeed
There is no winner

Submit

Source: 10th Iran Nationwide Internet Contest