← 返回题目列表

Codeforces · 1735/C

C. 相移

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

有一个字符串 $$$s$$$ 应该被加密。为此,将所有$$$26$$$小写英文字母按一定顺序排列成一圈,然后将$$$s$$$中的每个字母替换为按顺时针顺序排列的后面的字母,这样就得到了字符串$$$t$$$。

给你一个字符串 $$$t$$$。确定按字典顺序排列的最小字符串 $$$s$$$,它可能是给定字符串 $$$t$$$ 的原型。

字符串 $$$a$$$ 按字典顺序小于相同长度的字符串 $$$b$$$ 当且仅当:

- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 有一个字母,该字母在字母表中比 $$$b$$$ 中的相应字母更早出现。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 3 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 字符串 $$$t$$$ 的长度。

下一行包含长度为$$$n$$$的字符串$$$t$$$,包含小写英文字母。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一行,其中包含按字典顺序最小的字符串 $$$s$$$,该字符串可能是 $$$t$$$ 的原型。

示例

输入 #1

5
1
a
2
ba
10
codeforces
26
abcdefghijklmnopqrstuvwxyz
26
abcdefghijklmnopqrstuvwxzy

输出 #1

b
ac
abcdebfadg
bcdefghijklmnopqrstuvwxyza
bcdefghijklmnopqrstuvwxyaz

注意

在第一个测试用例中,我们不能使用字符串“a”,因为字母 a 会转换为自身。按字典顺序,第二个字符串“b”适合作为答案。

在第二个测试用例中,字符串“aa”不合适,因为 a 会转换为自身。 “ab”不合适,因为圆圈将用 $$$2$$$ 字母封闭,但它必须包含所有 $$$26$$$。下一个字符串“ac”是合适的。

下面您可以看到前三个测试用例的方案。不涉及的字母将被跳过,它们可以任意放置在间隙中。