Australian Voting

Time limit1sMemory limit128 MB

Summary

Simulate multi-round preferential voting: eliminate the lowest candidates each round and transfer their ballots until someone exceeds 50% or a tie remains.

Level: Medium4 of 10
Topics: Simulation, Implementation, Array, Greedy
Solved: No attempts yet

Problem

In Australian voting, each voter ranks all candidates in order of preference. Counting proceeds in rounds:

First, count only the first-choice vote on every ballot.
If some candidate has more than 50% of the votes, that candidate is elected.
Otherwise, every candidate tied for the fewest votes is eliminated. Each ballot cast for an eliminated candidate is transferred to its highest-ranked candidate who has not yet been eliminated.
Repeat until one candidate has more than 50% of the votes, or until all remaining candidates have the same number of votes (a tie).

Input

The first line contains an integer $n$ ( $1 \le n \le 20$ ), the number of candidates. Each of the next $n$ lines gives a candidate's name; a name may be up to 80 characters long and may contain any printable characters, including spaces. Up to 1000 ballots follow, one per line. Each ballot lists the integers $1$ through $n$ in some order: the first integer is the voter's first choice, the second integer the second choice, and so on.

Output

Print a single line with the name of the winner. If the process ends in a tie, print the name of every tied candidate on its own line, in the same order the candidates were given in the input.

Examples4

Example 1

Input

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

Expected output

John Doe

Example 2
Input
```
1
Alice
1
```
Expected output
```
Alice
```

Example 3

Input

3
Alpha
Beta
Gamma
1 2 3
1 3 2
1 2 3
2 1 3

Expected output

Alpha

Example 4
Input
```
2
Ada
Bob
1 2
2 1
```
Expected output
```
Ada
Bob
```