E. Замени на предыдущий, минимизируй
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$s$$$, состоящая из строчных латинских букв.

Можно применять следующую операцию:

  • выбрать один символ (от 'a' до 'z'), который хотя бы один раз встречается в строке. И все такие символы в строке заменить на предыдущий в алфавитном порядке по циклу. Например, все 'c' заменить на 'b' или все 'a' заменить на 'z'.

Задано число $$$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