1369: ShacozzZ的老鹰捉小鸡

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:9 Solved:5

Description

某天,ShacozzZ决定和队友玩老鹰捉小鸡。

经过几轮游戏下来,ShacozzZ发现了一个神奇的规律:所有组成小鸡的队友,当他们的名字的首字母按照队伍的顺序排列时,字典序越小队伍的稳定性就越高。但是由于大家不愿意花太多的精力放在调整队伍顺序上,所以ShacozzZ每一次只能指定第一个队友走到队伍的末尾。请问队伍稳定性最高时,名字首字母组成的字符串是什么?

更正式的说,现在有 $n$ 个队友,第 $i$ 个队友的名字是 $s_i$ ,队伍一开始是 $t=s_1[1]s_2[1]s_3[1]...s_n[1]$ ,ShacozzZ第一次操作可以使队列变为 $t=s_2[1]s_3[1]...s_n[1]s_1[1]$ ,第二次使队列变为 $t=s_3[1]...s_n[1]s_1[1]s_2[1]$ ,以此类推。请通过若干次操作使 $t$ 的字典序最小,并输出 $t$。

两个字符串 $s$ 和 $t$ ,当 $s[i]<t[i]$ 且 $\forall j<i,s[j]=t[j]$ 时,或者 $|s|<|t|$ 且 $\forall 1 \leq i \leq |s|,s[i]=t[i]$ 时,称$s$ 的字典序小于 $t$ 。例如 $abdc$ 的字典序小于 $abfa$ , $abc$ 的字典序小于 $abcaaa$

Input

第一行包含一个整数 $n(1 \leq n \leq 100)$ ,代表充当小鸡的队友。

接下来 $n$ 行,第 $i$ 行包含一个字符串 $s_i(1 \leq |s| \leq 100)$ ,代表初始位置为 $i$ 的队友的名字,保证字符串均为小写字符。

Output

第一行包含一个字符串,即最后的队伍顺序中所有人首字母所构成的字符串

Sample Input Copy

3
shacozzz
expmin
chenbi

Sample Output Copy

cse

HINT

队伍只有 $sec$ , $ecs$ , $cse$ 三种情况,显然 $cse$ 字典序最小

Source/Category