L. Last Christmas
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Back cover of Last Christmas, modified. Public Domain by Epic Records / CBS Records Inc.

A Christmas market is incomplete without live music, and you will find everything from out-of-tune renditions of "Jingle Bells" on a toy xylophone to professional arrangements of Bach's Christmas Oratorio. This year, Jonathan and Merle also want to earn some money playing Christmas songs, but they cannot even agree on which artists, let alone which songs. Jonathan likes Mariah Carey best, while Merle loves the whole Christmas album by the Goo Goo Dolls.

They decide to settle the discussion using statistics and the following strategy. They take $$$n$$$ past Christmas top-10 lists and count how often each artist appears. Note that an artist may appear multiple times on the same list. The artist with the highest number of appearances is clearly the best! If there is a tie, they look at the artist with the highest number of number 1 hits among the artists with the highest number of appearances. If there is still a tie, they look at highest number of number 2 hits among those, and so on.

Who is the best artist for the Christmas season?

Input

The input consists of:

  • One line with an integer $$$n$$$ ($$$1\leq n \leq 100$$$), the number of top-10 lists.
  • $$$n$$$ lines, each with $$$10$$$ strings $$$s$$$ ($$$1 \leq |s| \leq 20$$$), the first names of the artists of the top-10 list from $$$1$$$ to $$$10$$$. Each name only consists of English lowercase letters (a-z).$$$^{\text{∗}}$$$

$$$^{\text{∗}}$$$If Madonna does not need a last name, why would other artists need one?

Output

Output the name of the best artist according to the rules described above, or "tie" if there is no unique best artist.

Examples
Input
3
elton jose bowie eagles elvis wham nat joni bruce minnie
elton madonna wham elvis andy donny madonna aha chuck judy
madonna heart whitney chuck joni wham john yoko nsync stevie
Output
madonna
Input
3
maria a b wham c d e f maria wham
wham g h maria i j k l wham m
n o p q r s t u v maria
Output
tie
Input
2
b a b d e a e a b a
b b b e d a d a a a
Output
a
Note

In the first sample test, Madonna and Wham! both appear three times in total, but since Madonna has one more number 1 hit than Wham!, Madonna is the best artist.