Most Unique Species

You are given a list of tree species names. Two trees are compared by computing the length of their longest common subsequence (LCS). The LCS of two strings (X) and (Y) is defined as the longest sequence of characters that appear in both strings (not necessarily consecutively). For each species, compute the sum of the LCS lengths with every other species. The species with the minimum total LCS sum is considered the most unique. In case of a tie, choose the species that appears first in the input.

The LCS can be computed using dynamic programming with the following recurrence:

[ \text{dp}[i][j] = \begin{cases} 0, & \text{if } i = 0 \text{ or } j = 0,\ \text{dp}[i-1][j-1] + 1, & \text{if } X[i-1] = Y[j-1],\ \max(\text{dp}[i-1][j],, \text{dp}[i][j-1]), & \text{otherwise.} \end{cases} ]

Your task is to determine which species is the most unique based on the described criteria.

inputFormat

The first line contains an integer (n) ((1 \le n \le 10^3)), the number of species. Each of the following (n) lines contains a species name, which is a non-empty string.

outputFormat

Output the name of the species that has the minimum total longest common subsequence length when compared with all other species.## sample

3
oak
maple
fir

fir