Problem Description

There are $ N $ strings $ A_1, A_2, ..., A_N $ composed of uppercase and lowercase English letters.

The abbreviation of a string is defined as follows:

• For a string $ S $, any $ i, j, k $ satisfying $1 \leq i < j < k \leq |S|$ can form an abbreviation $ S_i S_j S_k $.

Find the 3-letter string that serves as the abbreviation for the most number of strings among $ A_1, A_2, ..., A_N $.

If there are multiple such strings, find the one that comes first in lexicographical order.

Note that in lexicographical order, uppercase letters always come before lowercase letters regardless of their type.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ : $ $ A_N $

Output Format

Find the 3-letter string that serves as the abbreviation for the most number of strings among $ A_1, A_2, ..., A_N $.

If there are multiple such strings, find the one that comes first in lexicographical order.

Sample Input and Output

Sample Input #1

4
aKIHaBaRa
aKIBa
aSaKUSa
SHINKIBA

Sample Output #1

KIB

Sample Input #2

3
abc
def
ghi

Sample Output #2

abc

Notes/Hints

Constraints

• $1 \leq N \leq 30000$
• $3 \leq |A_i|$
• $|A_1| + |A_2| + ... + |A_N| \leq 90000$
• $ A_i $ consists of uppercase and lowercase English letters

Sample Explanation 1

The abbreviations for three strings are KIB and aKa, but we should output the one that comes first in lexicographical order, which is KIB. Note that in lexicographical order, uppercase letters come before lowercase letters, so K comes before a.

见题面 Input 部分

见题面 Output 部分