D - Three Letters

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

英大文字および英小文字によって構成される N 個の文字列 A_1,A_2,...,A_N があります。

文字列の 略称 を以下のように定義します。

  • 文字列 S があるとき、1 \leq i < j < k \leq |S| を満たす任意の i,j,k に対し、S_i S_j S_kS の略称となる。

3 文字からなる文字列のうち、A_1,A_2,...,A_N のうち最も多くの文字列の略称となるものを求めてください。

ただし、複数ある場合は、辞書順で最初のものを求めてください。

なお、辞書順において、文字の種類にかかわらず英大文字は英小文字より必ず先になるとします。

制約

  • 1 \leq N \leq 30000
  • 3 \leq |A_i|
  • |A_1|+|A_2|+...+|A_N| \leq 90000
  • A_i は英大文字および英小文字からなる

入力

入力は以下の形式で標準入力から与えられる。

N
A_1
:
A_N

出力

3 文字からなる文字列のうち、A_1,A_2,...,A_N のうち最も多くの文字列の略称となるものを求めよ。

ただし、複数ある場合は、辞書順で最初のものを求めよ。


入力例 1

4
aKIHaBaRa
aKIBa
aSaKUSa
SHINKIBA

出力例 1

KIB

3 つの文字列の略称となるものは KIB,aKa ですが、これらのうち辞書順で最初の KIB を出力するとよいです。

辞書順において、英大文字は英小文字より必ず先になるので、Ka より先になることに注意してください。


入力例 2

3
abc
def
ghi

出力例 2

abc