该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P6140 [USACO07NOV] Best Cow Line S

题目背景

本题和 2007 年 12 月月赛金组同名题目 在题意上一致，唯一的差别是数据范围。

题目描述

给出 $N$个字符的序列。每次拿出原序列的头或尾的字符，插入到新序列的尾部。重复这一操作直到所有字符都插入新序列为止。

求新序列的最小字典序。

输入格式

第一行一个整数 $N \ (1 \leq N \leq 2000)$。

接下来 $N$ 行每行一个大写字母，表示初始队列。

输出格式

输出一个长度为 $N$ 的字符串，表示可能的最小字典序队列。

每输出 $80$ 个字母需要一个换行。

输入输出样例 #1

输入 #1

6
A
C
D
B
C
B

输出 #1

ABCBCD