← 返回题目列表

AtCoder · abc409_d

G. 字符串旋转

中文机器翻译题面 查看原题

分数: 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,按字典顺序最小。