Frequent Flyer

Problem Statement

Jackson is a frequent flyer and has been to many places around the world!

Jackson has a list of $n$ destinations he has flown to in the past. He wants to know which place he has flown to the most!

You are given a list of $n$ flight destinations you have been to in the past, output the most frequent place you have flown to.

Input

Your first line of input will contain a single integer $n$: the number of destinations flown to in total. Next, $n$ lines will follow, each containing a single string $f_i$: the name of a destination each.

Output

A single line, containing the name of the most frequent place Jackson has flown to.

If there is a tie, choose the place with the lexicographically (alphabetically) smallest name.

Constraints

• $1 \leq n \leq 10^5$
• $1 \leq |f_i| \leq 100$
• Each $f_i$ only contains English lower-case alphabet letters.

Example 1

10
japan
hongkong
japan
hongkong
france
germany
france
germany
japan
japan

japan

Explanation

Japan appeared more than any other location.

Example 2

4
asia
asia
antarctica
antarctica

antarctica

Explanation

There are $2$ places with the same number of flights flown to them.

Antartica is the alphabetically smaller destination, so it should be the final output over everything else.

Template

n = int(input())
f = [input() for _ in range(n)]
# Continue your code here and print your final answer!

Solution

If you'd like to view a sample solution to this tutorial question, please click the "Read Editorial" link to the right of the problem!