String and Operations

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$ 的字符串 $s$，其中每个字符都是拉丁字母表前 $k$ 个小写字母之一。你要依次进行 $n$ 次操作。

第 $i$ 次操作作用于最初位于第 $i$ 个位置的字符。你必须选择以下操作之一：

• 与当前相邻的前一个字符交换（若存在），记为 L；
• 与当前相邻的后一个字符交换（若存在），记为 R；
• 在前 $k$ 个字母组成的循环字母表中变成前一个字母，记为 D；
• 在这个循环字母表中变成后一个字母，记为 U；
• 不做任何事情，记为 0。

注意，交换后字符的位置可能改变，但第 $i$ 次操作始终作用于最初编号为 $i$ 的字符。

求完成全部操作后能够得到的字典序最小字符串。

输入格式

第一行包含测试用例数 $t$。

每个测试用例包含两行。第一行包含 $n,k$，第二行包含长度为 $n$ 的字符串 $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

数据范围

$1\le t\le1000$，$1\le n\le500$，$2\le k\le26$。字符串 $s$ 只含前 $k$ 个小写字母。