题目描述

$\red{FJ}$打算带他的$\red{N(1 <= N <= 30,000)}$头奶牛去参加一年一度的"全美农场主大奖赛"。在这场比赛中，每个参赛者都必须让他的奶牛排成一列，然后领她们从裁判席前依次走过。

今年，竞赛委员会在接受队伍报名时，采用了一种新的登记规则：他们把所有队伍中奶牛名字的首字母取出，按它们对应奶牛在队伍中的次序排成一列（比如说，如果$\red{FJ}$带去的奶牛依次为$\red{Bessie}$、$\red{Sylvia}$、$\red{Dora，}$登记人员就把这支队伍登记为$\red{BSD）}$。

登记结束后，组委会将所有队伍的登记名称按字典序升序排列，就得到了他们的出场顺序。 $\red{FJ}$最近有一大堆事情，因此他不打算在这个比赛上浪费过多的时间，也就是说，他想旧能早地出场。于是，他打算把奶牛们预先设计好的队型重新调整一下。

$\red{FJ}$的调整方法是这样的：每次，他在原来队列的首端或是尾端牵出一头奶牛，把她安排到新队列的尾部，然后对剩余的奶牛队列重复以上的操作，直到所有奶牛都被插到了新的队列里。这样得到的队列，就是$\red{FJ}$拉去登记的最终的奶牛队列。

接下来的事情就交给你了：对于给定的奶牛们的初始位置，计算出按照$\red{FJ}$的调整规则所可能得到的字典序最小的队列。

输入格式

第$\red{1}$行: 一个整数：$\red{N}$

第$\red{2..N+1}$行: 第$\red{i+1}$行仅有$\red{1}$个'$\red{A}$'..'$\red{Z}$'中的字母，表示队列中从前往后数第$\red{i }$头奶牛名字的首字母

输出格式

第$\red{1..??}$行: 输出$\red{FJ}$所能得到的字典序最小的队列。

每行（除了最后一行）输 出恰好$\red{80}$个'$\red{A}$'..'$\red{Z}$'中的字母，表示新队列中每头奶牛姓名的首 字母

样例

输入样例

6
A
C
D
B
C
B

输出样例

ABCBCD

提示

输入说明:

$\red{FJ}$有$\red{6}$头顺次排好队的奶牛：$\red{ACDBCB}$

输出说明：

操作数   原队列     新队列
   #1     ACDBCB
   #2      CDBCB     A
   #3      CDBC      AB
   #4      CDB       ABC
   #5      CD        ABCB
   #6       D        ABCBC
   #7                ABCBCD