← 返回题目列表

Codeforces · 1316/B

B. 字符串修改

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

Vasya 有一个长度为 $$$n$$$ 的字符串 $$$s$$$。他决定对字符串进行以下修改:

1. 选择一个整数 $$$k$$$, ($$$1 \leq k \leq n$$$)。
2. 对于从$$$1$$$到$$$n-k+1$$$的$$$i$$$,反转$$$s$$$的子串$$$s[i:i+k-1]$$$。例如,如果字符串 $$$s$$$ 为 qwer 并且 $$$k = 2$$$,则该字符串经历的一系列转换如下: qwer(原始字符串) wqer(反转长度为 $$$2$$$ 的第一个子字符串后) weqr(反转长度为 $$$2$$$ 的第二个子字符串后) werq(反转长度为 $$$2$$$ 的最后一个子字符串后)用 $$$k = 2$$$ 修改 $$$s$$$ 后的字符串是 werq。

Vasya想要选择一个$$$k$$$,使得经过上述修改后获得的字符串在$$$k$$$的所有选择中按字典顺序尽可能最小。在所有这些$$$k$$$中,他想选择最小的一个。由于他正忙于参加 Felicity 2020,他请求您的帮助。

当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:

- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中有一个字母比 $$$b$$$ 中的对应字母更早出现。

输入

每个测试包含多个测试用例。

第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5000$$$)。测试用例的描述如下。

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

每个测试用例的第二行包含 $$$s$$$ 由 $$$n$$$ 小写拉丁字母组成的字符串。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。

输出

对于每个测试用例输出两行:

在第一行中输出经过上述修改后可实现的字典顺序最小的字符串 $$$s'$$$。

在第二行中输出您选择用于执行修改的 $$$k$$$ ($$$1 \leq k \leq n$$$) 的适当值。如果 $$$k$$$ 的多个值给出了字典顺序最小的字符串,则输出其中 $$$k$$$ 的最小值。

示例

输入 #1

6
4
abab
6
qwerty
5
aaaaa
6
alaska
9
lfpbavjsm
1
p

输出 #1

abab
1
ertyqw
3
aaaaa
1
aksala
6
avjsmbpfl
5
p
1

注意

在第一个样本的第一个测试用例中,样本abab的字符串修改结果如下:

- $$$k = 1$$$ : abab
- $$$k = 2$$$ : 巴巴
- $$$k = 3$$$ : abab
- 对于 $$$k = 4$$$ : baba 对于 $$$k = 1$$$ 和 $$$3$$$,通过修改可实现的字典顺序最小的字符串是 abab。因此,需要实现的 $$$k$$$ 的最小值是 $$$1$$$。