← 返回题目列表

Codeforces · 1675/E

E. 替换为上一个,最小化

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

给你一个由小写拉丁字母组成的字符串$$$s$$$。

可以使用以下操作:

- 选择在字符串中至少出现一次的一个字符(从“a”到“z”)。并在循环中按字母顺序将字符串中的所有此类字符替换为前一个字符。例如,将所有“c”替换为“b”,或将所有“a”替换为“z”。

并且您将获得整数 $$$k$$$ — 可以执行的最大操作数。查找通过执行不超过 $$$k$$$ 操作可以获得的最小字典顺序可能的字符串。

如果存在索引 $$$k$$$ ($$$1 \le k \le n$$$) 使得 $$$a_1=b_1$$$,则字符串 $$$a=a_1a_2 \dots a_n$$$ 按字典顺序小于字符串 $$$b = b_1b_2 \dots b_n$$$, $$$a_2=b_2$$$,...,$$$a_{k-1}=b_{k-1}$$$,但$$$a_k < b_k$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中的测试用例数量。

接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$) - 字符串 $$$s$$$ 的大小以及可以对字符串 $$$s$$$ 执行的最大操作数。

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

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

输出

对于每个测试用例,输出按字典顺序排列的最小字符串,该字符串可以通过执行不超过 $$$k$$$ 操作从字符串 $$$s$$$ 获得。

示例

输入 #1

4
3 2
cba
4 5
fgde
7 5
gndcafb
4 19
ekyv

输出 #1

aaa
agaa
bnbbabb
aapp