← 返回题目列表

Codeforces · 1455/F

F. 字符串和操作

中文机器翻译题面 查看原题

给定一个由 $$$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