给定一个字符串 𝑠s，由 𝑛n 个字符组成。这些字符是拉丁字母表前 𝑘k 个小写字母。你需要对这个字符串执行 𝑛n 次操作。 在第 𝑖i 次操作中，你取出 最初位于 第 𝑖i 个位置的字符，并对其执行 以下 操作之一： • 将其与字符串中前一个字符交换（如果存在）。此操作用 L 表示； • 将其与字符串中后一个字符交换（如果存在）。此操作用 R 表示； • 循环地将其更改为字母表中前一个字符（b 变为 a，c 变为 b，依此类推；a 变为拉丁字母表的第 𝑘k 个字母）。此操作用 D 表示； • 循环地将其更改为字母表中下一个字符（a 变为 b，b 变为 c，依此类推；拉丁字母表的第 𝑘k 个字母变为 a）。此操作用 U 表示； • 什么也不做。此操作用 0 表示。 例如，假设初始字符串为 test，𝑘=20k=20，操作序列为 URLD。那么字符串的变换如下：

1. 第一次操作为 U，所以我们将 test 中下划线的字母更改为前 2020 个拉丁字母中的下一个字母，即 a。现在字符串为 aest;
2. 第二次操作为 R，所以我们将下划线的字母与字符串 aest 中的下一个字符交换。现在字符串为 aset;
3. 第三次操作为 L，所以我们将下划线的字母与字符串 aset 中的前一个字符交换（注意这现在是字符串的第 22 个字符，但它最初是第 33 个字符，因此对它执行第 33 次操作）。结果字符串为 saet;
4. 第四次操作为 D，所以我们将 saet 中下划线的字母更改为前 2020 个拉丁字母中的前一个字母，即 s。现在字符串为 saes。 执行操作序列的结果是 saes。 给定字符串 𝑠s 和 𝑘k 的值，找到在对 𝑠s 应用一系列操作后可以获得的字典序最小的字符串。 输入 第一行包含一个整数 𝑡t (1≤𝑡≤10001≤t≤1000) — 测试用例的数量。 每个测试用例由两行组成。第一行包含两个整数 𝑛n 和 𝑘k (1≤𝑛≤5001≤n≤500; 2≤𝑘≤262≤k≤26)。 第二行包含一个字符串 𝑠s，由 𝑛n 个字符组成。每个字符是拉丁字母表前 𝑘k 个字母（小写）的一个。 输出 对于每个测试用例，打印一行，包含从 𝑠s 使用一系列操作可以获得的字典序最小的字符串。 示例 Inputcopy Outputcopy 6 4 2 bbab 7 5 cceddda 6 5 ecdaed 7 4 dcdbdaa 8 3 ccabbaca 5 7 eabba aaaa baccacd aabdac aabacad aaaaaaaa abadb