← 返回题目列表

Codeforces · 1864/B

B. 交换和反转

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

给定一个由小写英文字母组成的字符串 $$$s$$$,长度为 $$$n$$$,以及一个整数 $$$k$$$。您可以一步执行以下两项操作中的任意一项:

- 选择一个索引 $$$i$$$ ($$$1 \le i \le n - 2$$$) 并交换 $$$s_{i}$$$ 和 $$$s_{i+2}$$$。
- 选择一个索引 $$$i$$$ ($$$1 \le i \le n-k+1$$$) 并反转由字符串的 $$$[i,i+k-1]$$$ 范围形成的字母顺序。形式上,如果字符串当前等于 $$$s_1\ldots s_{i-1}s_is_{i+1}\ldots s_{i+k-2}s_{i+k-1}s_{i+k}\ldots s_{n-1}s_n$$$,请将其更改为 $$$s_1\ldots s_{i-1}s_{i+k-1}s_{i+k-2}\ldots s_{i+1}s_is_{i+k}\ldots s_{n-1}s_n$$$。

您可以执行任意数量的步骤(可能为零)。您的任务是找到经过一定数量的步骤后可以获得的按字典顺序排列的最小字符串。

当且仅当以下条件成立时,字符串 $$$a$$$ 按字典顺序小于相同长度的字符串 $$$b$$$:

- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中的某个字母比 $$$b$$$ 中的相应字母更早出现。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k < n \le 10^5$$$)。

每个测试用例的第二行包含由小写英文字母组成的长度为$$$n$$$的字符串$$$s$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,在执行一些(可能是零)步骤后打印字典顺序最小的字符串。

示例

输入 #1

5
4 2
nima
5 3
panda
9 2
theforces
7 3
amirfar
6 4
rounds

输出 #1

aimn
aandp
ceefhorst
aafmirr
dnorsu

注意

在第一个测试用例中,我们可以使用以下操作获取字符串“aimn”:

1. 反转范围$$$[3,4]$$$。该字符串变成“niam”。
2. 交换 $$$s_1$$$ 和 $$$s_3$$$。该字符串变成“ainm”。
3. 反转范围 $$$[3,4]$$$。该字符串变成“aimn”。

可以证明,我们无法获得字典序上小于“aimn”的任何字符串。因此,“目标”就是答案。

在第二个测试用例中,我们可以使用以下操作获取字符串“aandp”:

1. 交换 $$$s_3$$$ 和 $$$s_5$$$。该字符串变成“paadn”。
2. 交换 $$$s_1$$$ 和 $$$s_3$$$。该字符串变成“aapdn”。
3. 交换 $$$s_3$$$ 和 $$$s_5$$$。该字符串变成“aandp”。

可以证明,我们无法获得字典序上小于“aandp”的任何字符串。因此,“aandp”就是答案。