The Voting Party!

Alice is organizing a small party for her friends, and she wants everyone to agree on one type of snack to serve. Each friend votes for their favorite snack by writing down their favourite snack. Alice then picks the most popular snack.

If there is a tie for the most votes, pick the snack with the shortest name.

It is guaranteed that all test cases will have only 1 correct answer (i.e., no test case will contain 2 or more snacks with the tied most number of votes, and have the same name length)

Input

The first line consists of an integer ~t~ ~(1 <= t <= 10^5)~, the number of people at the party.

Each line will contain a string ~S~, the name of a snack.

Output

For each test case, print the name of the snack that will be picked.

Example

Input

4
Kit-Kat
Oreos
Cookies
Oreos

Output

Oreos