Problem E: PIPI的字符串游戏

Problem E: PIPI的字符串游戏

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 214  Solved: 64
[Submit] [Status] [Web Board] [Creator:]

Description

输入一个n(2≤n≤1000,n是偶数)个字符串的集合D,找一个长度最短的字符串(不一定在D中出现)S,使得D中恰好一半串小于等于S,另一半串大于S。如果有多解,输出字典序最小的解。例如,对于{JOSEPHINE,JERRY},输出JF;对于{FRED,FREDDIE}输出FRED。字符串全部由大写字母构成。

Input

输入包含多组测试用例。
对于每一组用例,第一行包含一个正整数 n,代表字符串个数。
接下来n行每行输入一个有大写字母构成的字符串(串长不超过10000)。
一个单独的0代表输入结束。

Output

对于每一组样例,输出对应的S串。

Sample Input

4
FRED
SAM
JOE
MARGARET
2
FRED
FREDDIE
2
JOSEPHINE
JERRY
2
LARHONDA
LARSEN
0

Sample Output

K
FRED
JF
LARI