At the annual Valentines Day dance, a vote takes place to determine King and Queen Valentine!
The event organizers have decided to use the alternative vote to determine the winner of this contest.
In the alternative vote system, voters can rank their candidates rather than simply picking a single candidate.
Votes are tallied in the following way:
- Count the voters' first choices.
- Eliminate last place candidate by lowest number of votes. If there are multiple with the lowest number of votes, remove the candidate that appeared earliest in the input.
- Move each eliminated vote to its next choice. If the next choice is eliminated, move it to candidate after. Continue moving until a candidate that is not eliminated.
- Repeat 2 and 3 until there is a single candidate left.
If, at any point, a voter runs out of ranked candidates, the voter is removed.
Can you determine the winner of the vote?
The first line will contain two integers, ~N, M\ (1 \le N \le 20, 1 \le M \le 10^4)~, the number of candidates and the number of voters, respectively.
The next ~N~ lines will contain a single string of letters, indicating a candidate name. It is guaranteed that a candidate's name is less than or equal to ~20~ characters.
The next ~M~ lines will contain an integer ~X\ (1 \le X \le 20)~, indicating the number of candidates that the voter ranked followed by ~X~ space separated strings of candidate names, where the ~j~th candidate is the ~j~th choice of the voter. It is guaranteed that each candidate exists.
A single string, the winner of the vote. It is guaranteed there will always be a winner.
Subtask 1 [20%]
~N, M \le 9~
Subtask 2 [80%]
No additional constraints.
Sample Input 1
2 3 Rabbit Fox 2 Fox Rabbit 2 Rabbit Fox 2 Rabbit Fox
Sample Output 1
Explanation for Sample 1
Rabbit earned a majority of first choice votes, so he wins.
Sample Input 2
4 8 Yellow Pink Blue Red 3 Red Yellow Blue 4 Red Blue Pink Yellow 4 Red Blue Pink Yellow 2 Blue Pink 2 Yellow Pink 1 Pink 1 Pink 2 Yellow Blue
Sample Output 2
Explanation for Sample 2
The first choices tally to
Yellow: 2 Pink: 2 Blue: 1 Red: 3
On round one, Blue is eliminated and Blue's vote goes to Pink. (Yellow=2, Pink=3, Red=3)
On round two, Yellow is eliminated. Only one Yellow voter had a second preference, and it goes to Pink. (Pink=4, Red=3)
Now, Pink has the majority of votes so Pink wins.