时间限制:1000ms  空间限制:256MB

题目描述

约翰打算带他的N(1≤N≤2000)头奶牛去参加一年一度的“全美农场主大奖赛”，在这场比赛中，每个参赛者都必须让他的奶牛排成一列，然后领她们从裁判席前依次走过.今年，竞赛委员会在接受队伍报名时，采用了一种新的登记规则:他们把所有队伍中奶牛名字的首字母取出，按它们对应奶牛在队伍中的次序排成一列．登记结束后，组委会将所有队伍的登记名称按字典序升序排列，就得到了他们的出场顺序.约翰最近有一大堆事情，因此他不打算在这个比赛上浪费过多的时间，也就是说，他想尽可能早地出场．于是，他打算把奶牛们预先设计好的队型重新调整一下.约翰的调整方法是这样的:每次，他在原来队列的首端或是尾端牵出一头奶牛，把她安排到新队列的尾部，然后对剩余的奶牛队列重复以上的操作，直到所有奶牛都被插到了新的队列里.这样得到的队列，就是约翰拉去登记的最终的奶牛队列.接下来的事情就交给你了:对于给定的奶牛们的初始位置，计算出按照约翰的调整规则所可能得到的字典序最小的队列.

输入格式

第1行输入一个整数N，之后N行每行输入一个大写字母，表示了初始序列.

输出格式

得到的最小字典序的序列．每输出80个字母需要一个换行.

样例

输入#1

6
A
C
D
B
C
B

输出#1

ABCBCD

题目来源

USACO 2007 NOV