P1063康神开播了（kskbl）

【题目背景】

ZmjjKK 准备在 Gioush 大队营地开播。为了不让异常口令被发现，需要调整尚未记录的片段，并使最终记录字典序尽可能小。

【题目描述】

给定一个由小写英文字母组成的字符串 $S$，以及初始为空的字符串 $R$。不断对 $S$ 执行操作，直到 $S$ 为空。每次可选择：

1. 删除 $S$ 的第一个字符，并把它添加到 $R$ 末尾；
2. 删除 $S$ 的最后一个字符，并把它添加到 $R$ 末尾；
3. 选择两个非空字符串 $A,B$，满足 $S=ABA^R$，令 $S=B$，并把 $A$ 添加到 $R$ 末尾。其中 $A^R$ 表示 $A$ 的反转串。

求所有合法操作方案中最终字符串 $R$ 的字典序最小值。

【输入格式】

第一行包含两个非负整数 $c,T$，分别表示测试点编号和测试数据组数。样例中 $c=0$，正式测试数据中 $1\le c\le20$。

接下来 $T$ 行，每行包含一个由小写英文字母组成的字符串 $S$。

【输出格式】

对于每组测试数据输出一行，表示能够得到的字典序最小的 $R$。

【样例输入】

10 62cba3zayaz4aaaaa5xazbx6ababa7aa

【样例输出】

1abc2zaay3aaa4xabz5aaba6aa

对于 $100\%$ 的数据，$1\le T\le10^5$，$1\le |S_i|\le5\times10^5$，且 $\sum |S_i|\le5\times10^5$。