UOJ Logo

NOI.AC

1S 512MB

#1586. 生成最小字符串

Statistics

题目描述

给定一个长度为$n$的字符串$S$。你只能进行如下操作

从$S$的头部删除一个字符加入$T$ 从$S$的尾部删除一个字符加入$T$

现在请按照该规则输出字典序最小的字符串$T$

输入格式

第一行一个整数$n$ 接下来$n$行每行一个大写字符

输出格式

输出若干行,字典序最小字符串$T$,每$80$个字符输出一个换行。

输入样例1

6
A
C
D
B
C
B

输出样例1

ABCBCD

样例解释

第一次删除首部的A,$S$变为CDBCB,$T$变为A 第二次删除尾部的B,$S$变为CDBC,$T$变为AB 第三次删除尾部的C,$S$变为CDB,$T$变为ABC 第四次删除尾部的B,$S$变为CD,$T$变为ABCB 第五次删除首部的C,$S$变为D,$T$变为ABCBC 第五次删除首部的D,$S$变为`,$T$变为ABCBCD`

数据规模

对于$100\%$的数据$1 \leq n \leq 30000 $