String Modification

题面翻译

题目描述

Vasya 有一个长度为 $n$ 的字符串 $s$。他想要对它进行以下的修改：

1. 选择一个整数 $k$ 且 $1\leq k\leq n$。
2. 让 $i$ 从 $1$ 循环到 $n - k + 1$，每一次反转 $s$ 在 $[i,i + k - 1]$ 范围中的子串。

比如说，字符串 $s$ 是 $\texttt{qwer}$ 且 $k = 2$，以下就是 $s$ 被修改的过程：

• $\texttt{qwer}$（原字符串）
• $\texttt{wqer}$（旋转了第一个长为 $2$ 的子串）
• $\texttt{weqr}$（旋转了第二个长为 $2$ 的子串）
• $\texttt{werq}$（旋转了最后一个长为 $2$ 的子串）

所以，$s$ 经过 $k = 2$ 的一系列变化后最终会变成 $\texttt{werq}$。

Vasya 希望选择一个 $k$,使得经过上述变化的字符串字典序最小。如果多个不同的 $k$ 都能满足要求，他想要取最小的一个。他正忙着参加 Felicity 2020，于是他叫你来帮他。

一个字符串 $a$ 比 $b$ 字典序更小需要以下条件中只有一个满足：

• $a$ 是 $b$ 的前缀，但 $a \ne b$;
• 在从左往右 $a$ 和 $b$ 第一个不同的位置，$a$ 上的字符在字母表中比 $b$ 上字符更靠前。

输入格式

每一个测试点有多组数据。

第一行有一个整数 $t(1\leq t\leq 5000)$ 表示数据组数。

每组数据第一行包含一个整数 $n$，表示字符串长度。

第二行包含一个有 $n$ 个小写英文字母的字符串 $s$。

保证每组数据的 $n$ 不会超过 $5000$。

输出格式

对于每一组数据打印两行：

第一行是可以达到的字典序最小的字符串 $s'$。

第二行是与之相应的 $k(1\leq k\leq n)$ 用来进行修改。如果多个 $k$ 都可以达到字典序最小的字符串，请打印最小的一个 $k$。

题目描述

Vasya has a string $s$ of length $n$ . He decides to make the following modification to the string:

1. Pick an integer $k$ , ( $1 \leq k \leq n$ ).
2. For $i$ from $1$ to $n-k+1$ , reverse the substring $s[i:i+k-1]$ of $s$ . For example, if string $s$ is qwer and $k = 2$ , below is the series of transformations the string goes through:

• qwer (original string)
• wqer (after reversing the first substring of length $2$ )
• weqr (after reversing the second substring of length $2$ )
• werq (after reversing the last substring of length $2$ )

Hence, the resulting string after modifying $s$ with $k = 2$ is werq.

Vasya wants to choose a $k$ such that the string obtained after the above-mentioned modification is lexicographically smallest possible among all choices of $k$ . Among all such $k$ , he wants to choose the smallest one. Since he is busy attending Felicity 2020, he asks for your help.

A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds:

• $a$ is a prefix of $b$ , but $a \ne b$ ;
• in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$ .

输入格式

Each test contains multiple test cases.

The first line contains the number of test cases $t$ ( $1 \le t \le 5000$ ). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ( $1 \le n \le 5000$ ) — the length of the string $s$ .

The second line of each test case contains the string $s$ of $n$ lowercase latin letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$ .

输出格式

For each testcase output two lines:

In the first line output the lexicographically smallest string $s'$ achievable after the above-mentioned modification.

In the second line output the appropriate value of $k$ ( $1 \leq k \leq n$ ) that you chose for performing the modification. If there are multiple values of $k$ that give the lexicographically smallest string, output the smallest value of $k$ among them.

样例 #1

样例输入 #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

提示

In the first testcase of the first sample, the string modification results for the sample abab are as follows :

• for $k = 1$ : abab
• for $k = 2$ : baba
• for $k = 3$ : abab
• for $k = 4$ : babaThe lexicographically smallest string achievable through modification is abab for $k = 1$ and $3$ . Smallest value of $k$ needed to achieve is hence $1$ .