给定一个由 $$$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中的下一个字母交换。现在字符串已设置;
3.第三个操作是L,所以我们将带下划线的字母与字符串集合中的前一个字母交换(注意,现在这是字符串的$$$2$$$-nd字符,但它最初是$$$3$$$-rd,所以对其执行$$$3$$$-rd操作)。得到的字符串是saet;
4、第四个操作是D,所以我们把saet中带下划线的字母改为前$$$20$$$拉丁字母中的前一个,即s。该字符串现在是 saes。
执行该操作序列的结果是 saes。
给定字符串$$$s$$$和$$$k$$$的值,找到对$$$s$$$应用一系列操作后可以获得的按字典顺序最小的字符串。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例由两行组成。第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 500$$$; $$$2 \le k \le 26$$$)。
第二行包含一个由 $$$n$$$ 个字符组成的字符串 $$$s$$$。每个字符都是拉丁字母表中 $$$k$$$ 的第一个字母(小写)。
输出
对于每个测试用例,打印一行,其中包含可以使用一系列操作从 $$$s$$$ 获取的字典顺序最小的字符串。
示例
输入 #1
6 4 2 bbab 7 5 cceddda 6 5 ecdaed 7 4 dcdbdaa 8 3 ccabbaca 5 7 eabba
输出 #1
aaaa baccacd aabdac aabacad aaaaaaaa abadb