分数: 400 点
问题陈述
给你一个字符串 S=S_1S_2\dots S_N 长度 N 由小写英文字母组成。您将执行以下操作 S 恰好一次:
- 选择一个连续的子字符串 S 长度至少 1 并循环左移 1。即选择整数 1 \leq \ell \leq r \leq N,插入 S_\ell 在右侧 r第一个字符 S,然后删除 \ell第一个字符 S.
在所有可能的字符串中查找字典顺序最小的字符串 运行后即可变成 S 。
你被给予 T 测试用例,因此解决每个用例。
约束
- 1 \leq T \leq 10^5
- 1 \leq N \leq 10^5
- S 是一个长度为的字符串 N 由小写英文字母组成。
- T 和 N 是整数。
- 总和 N 单个输入文件中的所有测试用例最多 10^5.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例 \mathrm{case}_i\;(1 \leq i \leq T) 按以下格式给出:
N S
输出
输出 T 行。的 i-th (1 \leq i \leq T) 行应包含以下问题的答案 \mathrm{case}_i.
示例输入 1
3 7 atcoder 1 x 5 snuke
示例输出 1
acodert x nsuke
- 在第一个测试用例中,从 2到 7第一个字符给出
acodert,按字典顺序最小。 - 在第二个测试用例中,无论你如何操作,你都会得到
x. - 在第三个测试用例中,从 1st 到 2nd 字符给出
nsuke,按字典顺序最小。