CF1455F String and Operations

给定一个由 $n$ 个字符组成的字符串 $s$。这些字符均为拉丁字母表前 $k$ 个小写字母中的某一个。你需要对该字符串进行 $n$ 次操作。 在第 $i$ 次操作时，你需要对最初位于第 $i$ 个位置的字符执行以下操作之一： - 与前一个字符交换（如果存在）。该操作用 L 表示； - 与后一个字符交换（如果存在）。该操作用 R 表示； - 在字母表中循环变为前一个字母（b 变为 a，c 变为 b，依此类推；a 变为拉丁字母表的第 $k$ 个字母）。该操作用 D 表示； - 在字母表中循环变为下一个字母（a 变为 b，b 变为 c，依此类推；第 $k$ 个字母变为 a）。该操作用 U 表示； - 什么都不做。该操作用 0 表示。 例如，假设初始字符串为 test，$k = 20$，操作序列为 URLD。那么字符串的变化过程如下： 1. 第一次操作是 U，将 test 中被下划线标记的字母变为前 $20$ 个拉丁字母中的下一个字母，即 a。此时字符串变为 aest； 2. 第二次操作是 R，将 aest 中被下划线标记的字母与下一个字符交换。此时字符串变为 aset； 3. 第三次操作是 L，将 aset 中被下划线标记的字母与前一个字符交换（注意此时它是字符串的第 $2$ 个字符，但它最初是第 $3$ 个字符，因此第 $3$ 次操作仍然作用于它）。此时字符串变为 saet； 4. 第四次操作是 D，将 saet 中被下划线标记的字母变为前 $20$ 个拉丁字母中的前一个字母，即 s。此时字符串变为 saes。 执行完操作序列后，最终得到的字符串为 saes。 给定字符串 $s$ 和 $k$ 的值，求通过一系列操作后能够得到的字典序最小的字符串。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 每个测试用例包含两行。第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 500$；$2 \le k \le 26$）。 第二行包含一个长度为 $n$ 的字符串 $s$。字符串中的每个字符均为前 $k$ 个拉丁小写字母之一。

对于每个测试用例，输出一行，表示通过一系列操作后能够得到的字典序最小的字符串。

由 ChatGPT 4.1 翻译