Дана строка $$$s$$$, состоящая из строчных латинских букв.
Можно применять следующую операцию:
Задано число $$$k$$$ — максимальное количество операций, которое можно совершить. Найдите минимальную лексикографически строку, которую можно получить, совершив не более $$$k$$$ операций.
Строка $$$a=a_1a_2 \dots a_n$$$ лексикографически меньше строки $$$b = b_1b_2 \dots b_n$$$, если существует такой индекс $$$k$$$ ($$$1 \le k \le n$$$), что $$$a_1=b_1$$$, $$$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$$$.
Во второй строке каждого набора записана строка $$$s$$$ длины $$$n$$$, состоящая из строчных латинских букв.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите лексикографически минимальную строку, которую можно получить из строки $$$s$$$, применив не более чем $$$k$$$ операций.
4 3 2 cba 4 5 fgde 7 5 gndcafb 4 19 ekyv
aaa agaa bnbbabb aapp
| Codeforces Round 787 (Div. 3) |
|---|
| Закончено |
