{"problem":{"name":"小园香径独徘徊","description":{"content":"有两个字符串 $S,T$，一开始给定 $S$，$T$ 为空串。每次你可以执行以下三种操作，直到 $S$ 变为空串： 1. 删去 $S$ 的第一个字符，并将这个字符插入 $T$ 的开头； 1. 删去 $S$ 的第一个字符，并将这个字符插入 $T$ 的末尾； 1. 删去 $S$ 的最后一个字符，并将这个字符插入 $T$ 的开头。 a3 想知道，$S$ 变为空串后，可以构成的字典序最小的 $T$。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9348"},"statements":[{"statement_type":"Markdown","content":"有两个字符串 $S,T$，一开始给定 $S$，$T$ 为空串。每次你可以执行以下三种操作，直到 $S$ 变为空串：\n\n1. 删去 $S$ 的第一个字符，并将这个字符插入 $T$ 的开头；\n1. 删去 $S$ 的第一个字符，并将这个字符插入 $T$ 的末尾；\n1. 删去 $S$ 的最后一个字符，并将这个字符插入 $T$ 的开头。\n\na3 想知道，$S$ 变为空串后，可以构成的字典序最小的 $T$。\n\n## Input\n\n**本题有多组测试数据。**\n\n第一行一个整数 $Q$，表示测试数据组数。\n\n对于每组测试数据，一行一个字符串 $S$。\n\n## Output\n\n对于每组测试数据，一行一个字符串，表示可以构成的字典序最小的 $T$。\n\n[samples]\n\n## Background\n\n徘徊在一条幽深的小径上，拾起记忆的碎片，将它们放入两个长长的口袋中。\n\n将它们收集完倒出来后，会拼成什么样的故事呢？\n\n## Note\n\n**【样例 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$ 仅由小写字母构成。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9348","tags":["字符串","贪心","洛谷原创","后缀自动机 SAM","O2优化","后缀数组 SA","洛谷月赛"],"sample_group":[["2\nababdca\ndcbcadb","aaabbdc\nabbcdcd"]],"created_at":"2026-03-03 11:09:25"}}