{"raw_statement":[{"iden":"background","content":"徘徊在一条幽深的小径上，拾起记忆的碎片，将它们放入两个长长的口袋中。\n\n将它们收集完倒出来后，会拼成什么样的故事呢？"},{"iden":"statement","content":"有两个字符串 $S,T$，一开始给定 $S$，$T$ 为空串。每次你可以执行以下三种操作，直到 $S$ 变为空串：\n\n1. 删去 $S$ 的第一个字符，并将这个字符插入 $T$ 的开头；\n1. 删去 $S$ 的第一个字符，并将这个字符插入 $T$ 的末尾；\n1. 删去 $S$ 的最后一个字符，并将这个字符插入 $T$ 的开头。\n\na3 想知道，$S$ 变为空串后，可以构成的字典序最小的 $T$。"},{"iden":"input","content":"**本题有多组测试数据。**\n\n第一行一个整数 $Q$，表示测试数据组数。\n\n对于每组测试数据，一行一个字符串 $S$。"},{"iden":"output","content":"对于每组测试数据，一行一个字符串，表示可以构成的字典序最小的 $T$。"},{"iden":"note","content":"**【样例 1 解释】**\n\n- 对于 $\\texttt{ababdca}$，依次进行第 $1,2,1,2,2,2,1$ 种操作，即可得到 $\\texttt{aaabbdc}$。\n- 对于 $\\texttt{dcbcadb}$，依次进行第 $1,1,1,2,3,1,2$ 种操作，即可得到 $\\texttt{abbcdcd}$。\n\n**【数据规模与约定】**\n\n**本题采用捆绑测试。**\n\n-  Subtask 1（5 points）：$S$ 由至多两种字符构成。\n-  Subtask 2（10 points）：$\\sum |S|\\le 12$。\n-  Subtask 3（15 points）：$\\sum |S|\\le 100$。\n-  Subtask 4（25 points）：$\\sum |S|\\le 3\\times 10^3$。\n-  Subtask 5（20 points）：$\\sum |S|\\le 2\\times 10^5$。\n-  Subtask 6（25 points）：无特殊限制。\n\n对于 $100\\%$ 的数据，$1\\le Q\\le 3\\times 10^5$，$1\\le |S|\\le 10^6$，$1\\le \\sum |S|\\le 2\\times 10^6$，$S$ 仅由小写字母构成。"}],"translated_statement":null,"sample_group":[["2\nababdca\ndcbcadb","aaabbdc\nabbcdcd"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}