配点 : 500 点
問題文
由大写和小写英文字母组成的 N 个字符串。 A_1,A_2,...,A_N 的字符串
的 略称 定义如下。当存在
- 文字列 S 时,1 \leq i < j < k \leq |S| 满足的不论的 i,j,k ,S_i S_j S_k 是 仅由 S 的简称。由
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 输出就可以了。
按字典顺序,大写字母始终位于小写字母之前,因此
请注意,它位于K 是a 之前。
入力例 2
3 abc def ghi
出力例 2
abc