## Girls Invitational '18 J4 - Elections in Ada Land

View as PDF

Points: 5
Time limit: 2.0s
Memory limit: 256M

Problem type

The country of Ada Land is holding their general election!

Ada Land uses a different voting system than Canada, and you have been tasked with figuring out the winners.

In the Ada Landian elections, one election is held for each of the $$N$$ ridings. Each riding elects one candidate. Each election has $$V_i$$ voters and $$C_i$$ candidates.

Each of the $$V_i$$ voters writes the names of all $$C_i$$ candidates in order of preference on their ballot.

In order to be elected, a candidate must get at least $$50\%$$ of the votes. If nobody has enough votes, the candidate in last place is eliminated, and their voters ballots are transferred to their next non-eliminated choice.

In the case of a tie during any point in the count, the candidate whose name was listed first in the list of candidates ranks higher.

#### Input Specification

The first line contains $$N\ (1 \le N \le 500)$$, the number of elections to be held. The input for $$N$$ elections follows.

Each election input start with $$C_i$$, the number of candidates in the $$i^{th}$$ election. $$1 \le C_i\le 1000$$.

The next line contains $$C_i$$ alphanumeric names, separated by spaces. It is guaranteed that in any single election, no two candidates will have the same name.

The next line contains $$V_i$$, the number of voters in the $$i^{th}$$ election. $$1 \le V_i \le 1000$$.

The next $$V_i$$ lines contain the ballot of each voter. Each ballot is a list of all candidate’s names separated by a single space. Names are in order of the voter’s preference, with the most preferred candidate’s name first and the least preferred candidate’ name last.

Additionally: $\displaystyle N \times \prod_{i=1}^N C_i \times \prod_{i=1}^N V_i \le 1\ 000\ 000$

#### Output Specification

Output the names of the elected candidates in the same order that the elections were given in the input.

#### Sample Input

2
4
Ada Lovelace Grace Hopper
7
Ada Lovelace Grace Hopper
Ada Lovelace Grace Hopper
Ada Lovelace Grace Hopper
Grace Ada Lovelace Hopper
Grace Lovelace Ada Hopper
Lovelace Ada Grace Hopper
Lovelace Ada Grace Hopper
3
C B A
3
A B C
B A C
C B A

#### Sample Output

Ada
B