3969. 字串加密

【题目背景】

遗迹中，S 先生拿着破损的字符串找到了你，这是在末日中唯一能够携带的物质了。

为了保护仅存的字符串，S 先生将其进行了 Super Encrypt 方式的加密。

不料，加密后的字符串被三体人发现，他们正在试图破解这个末日字串。

【题目描述】

S 先生有一个仅包含小写字母的原始字符串 $s$。

将原串 $s$ 按照某种方式加密得到了仅包含小写字母的字符串 $t$，三体人并不知道原串 $s$。

但是通过某种奇妙的方式，三体人得知了这个原串的加密方式：

将 $26$ 个小写英文字母的无序排列首尾相接成一个字符环（三体人并不知道它们排列的顺序），然后将原串 $s$ 中的每个字符都转换为字符环中其顺时针方向的下一个字符，由此得到加密后的字符串 $t$。

对于以上的加密方式，有以下两个形式化的说明：

$\mathbf{1.}$ 形式化地说，若 $26$ 个小写字母的排列表示为 $\{p_i\}$，那么在 $\{p_i\}$ 首尾相接成的字符环中 $p_n$ 的下一个为 $p_1$（反之亦然），加密方式是将原串 $s$ 中所有的 $p_i$ 转换为 $p_i$ 的顺时针方向的下一个字符 $p_{i+1\;\bmod\;n}$，由此得到加密后的字符串 $t$。

$\mathbf{2.}$ 换种方式来说，若 $26$ 个小写字母的排列表示为 $\{q_i\}$，不妨令 $f_{q_i}$ 表示在 $\{q_i\}$ 首尾相接成的字符环中 $q_i$ 的顺时针方向的下一个字符 $q_{i+1\;\bmod\;n}$，则加密后的字符串 $t_i=f_{s_i}$，由此得到加密后的字符串 $t$。

现在给出原串 $s$ 被加密之后得到的字符串 $t$。

你需要在三体人之前求出所有可能的原串 $s$ 中，字典序最小的那一个。

字典序说明：若 $\left | a \right | < \left | b \right |$ 或者 $\exists i \in \mathbb{N^* },a_i < b_i,a_{1 \dots i - 1} = b_{1 \dots i - 1}$，则我们称字符串 $a$ 的字典序小于字符串 $b$。

提示：

$\mathbf{1.}$ 可以证明，对于任意字符串 $t$，都至少存在一个可以加密为 $t$ 的原串 $s$。

$\mathbf{2.}$ $\left | s \right |$ 表示字符串 $s$ 的长度。

$\mathbf{3.}$ $\exists i \in \mathbb{N^* },p(i)$ 表示存在一个正整数 $i$ 满足条件 $p(i)$。

【输入格式】

本题包含多组数据。

输入共 $2 \times T+1$ 行。

第一行输入一个正整数 $T$，表示测试数据的组数。

对于每组数据（接下来 $2 \times T$ 行）：

第一行输入一个正整数 $n$，表示字符串 $t$ 的长度。

第二行输入一个字符串 $t$，表示原串 $s$ 被加密后的字符串。

【输出格式】

输出共 $T$ 行。

第 $i$ 行输出一个原串 $s$，表示加密后的字符串 $t$ 的原串中字典序最小的那一个。

【样例1输入】

5
1
a
2
ps
5
lsodj
10
doodjgufhs
26
abcdefghijklmnopqrstuvwxyz

【样例1输出】

b
ab
abced
abbacdegfh
bcdefghijklmnopqrstuvwxyza

【样例2】

样例下载

【样例说明】

对于样例 $1$：

第一组数据可以按以下方式加密：$b \to a$，可以证明此方式为最优解。

第二组数据可以按以下方式加密：$a \to p$，$b \to s$，可以证明此方式为最优解。

【数据规模与约定】

对于前 $5\%$ 的数据保证：$T = 0$。

对于前 $20\%$ 的数据保证：$0 \le n \le 2$。

对于另 $20\%$ 的数据保证：字符串中仅包含 $a,b$ 两种字符。

对于前 $60\%$ 的数据保证：$0 \le n \le 25$。

对于 $100\%$ 的数据保证：$0 \le T \le 3 \times 10^4$，$1 \le n \le 10^5$，$T \le \sum n \le 2 \times 10^5$。

【来源】

2024年校际联合邀请赛 入门组-第1场 Task3