Find the Most Frequent Compressed Word

After coming home, little X stared at his drowsy English notes and became confused. In his sleep, he often wrote a letter several times consecutively. For example, he might write she as shhe or even ssshee.

However, he vaguely remembers that only one key vocabulary word was covered in class. To identify this word, he first wants to compress each word by replacing consecutive duplicate letters with a single instance. For instance, the word coool is compressed to col and aabbaa is compressed to aba. In mathematical notation, if a word consists of characters \( c_1, c_2, \ldots, c_n \), then its compressed form is generated by replacing any maximal contiguous block of identical characters \( c_i \) with a single \( c_i \); that is, for any block \( c_i, c_i, \ldots, c_i \), it is compressed to just \( c_i \).

Your task is to help little X by identifying the word that occurs most frequently after the compression process. It is guaranteed that the most frequent compressed word is unique.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), representing the number of words. Each of the following n lines contains a non-empty word consisting of lowercase English letters.

outputFormat

Output the most frequent compressed word.

sample

5
she
shhe
sshee
hello
hhhello

she