Simulate an instant runoff election It's the election! The area which we are in implements the system of voting called instant runoff (sometimes called alternative vote or preferential voting). Each voter orders each candidate from most preferred to least preferred, marking a "1" for their most preferred candidate,
a "2" for their second candidate, and so forth until each candidate is numbered. I'll let this friendly koala explain the rest:



(Image modified from original by Patrick Alexander, used under the CC BY-NC-SA 3.0 AU licence). 

If you prefer your instant runoff explanation in text form, there's also the Wikipedia article.

(Note: It's also possible, although unlikely, for there to be two or more candidates with the least votes. In these situations, choose one of them randomly at equal probabilities and eliminate them.)

In this challenge, the first line of input is a list of strings, which are the names of the candidates for the election. In these examples I've used pipe delimited values, although feel free to adjust the input format to suit your language.

The Omitted Anti-neutrino|Placazoa|Alexander the Awesome|Tau Not Two|Semolina Sorcerer


Following that are n lines of input which are also lists of strings, each which represents a single vote. The first entry represents that votes #1 preference, the next the #2 preference, etc. For example:

Alexander the Awesome|Semolina Sorcerer|Tau Not Two|Placazoa|The Omitted Anti-neutrino


would mean that that particular vote has Alexander as their first preference, Semolina Sorcerer as their second, Tau Not Two as their third, etc. You can assume that every vote will contain every candidate, and that there will be no blank or incomplete votes. 

Given the votes as input, your program or function should then output the winner of the election. You can find an ungolfed reference implementation in Python 3 here.

Example Inputs and Outputs

Input

Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Portal Butter|Alexander the Awesome|Dionysius|Red Trainmen
Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Portal Butter|Red Trainmen|Alexander the Awesome|Dionysius
Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Alexander the Awesome|Red Trainmen|Portal Butter|Dionysius
Red Trainmen|Alexander the Awesome|Dionysius|Portal Butter
Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Red Trainmen|Dionysius|Portal Butter|Alexander the Awesome
Alexander the Awesome|Dionysius|Red Trainmen|Portal Butter
Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Alexander the Awesome|Red Trainmen|Dionysius|Portal Butter


Output

Alexander the Awesome


Input

Depressed Billy|Sighted Citrus|Frosty Fox|Electronic Accident
Frosty Fox|Sighted Citrus|Electronic Accident|Depressed Billy
Frosty Fox|Depressed Billy|Sighted Citrus|Electronic Accident
Depressed Billy|Electronic Accident|Sighted Citrus|Frosty Fox
Depressed Billy|Sighted Citrus|Electronic Accident|Frosty Fox
Depressed Billy|Electronic Accident|Sighted Citrus|Frosty Fox
Electronic Accident|Frosty Fox|Depressed Billy|Sighted Citrus
Sighted Citrus|Frosty Fox|Electronic Accident|Depressed Billy
Frosty Fox|Depressed Billy|Sighted Citrus|Electronic Accident
Sighted Citrus|Electronic Accident|Frosty Fox|Depressed Billy
Frosty Fox|Electronic Accident|Depressed Billy|Sighted Citrus
Sighted Citrus|Frosty Fox|Depressed Billy|Electronic Accident


Output

Sighted Citrus or Frosty Fox (randomly)

Input

You can get the last input set here. It is one of the voting areas of a recent Australian election, and consists of 63 428 votes. 

Output

Ross HART
Pyth - 30 bytes
Will refactor it. Infers first line from rest of input.
WgclQ2leKlD.gkhMQ=Q-RhhJKQ;hhJ

Test Suite.