Most Frequent Word

You are given a string S consisting only of lowercase English letters and spaces. Your task is to find the word that appears most frequently in the string. In the case of a tie, the word that appears first in the string should be returned.

The problem can be formalized as follows:

Given an integer \(N\) (the length of the string) and a string \(S\) of length \(N\), find the word \(w\) such that its frequency \(f(w)\) is maximized. If there is more than one candidate with \(f(w) = \max_{w'} f(w')\), then choose the candidate that appears first in \(S\).

inputFormat

The input is given from stdin and consists of two lines:

• The first line contains a single integer N, representing the length of the string.
• The second line contains the string S consisting only of lowercase English letters and spaces.

outputFormat

Output the most frequently occurring word to stdout. In the case of a tie, output the word that appears first in the string.

15
cat bat cat bat cat

cat