Дана строка $$$s$$$ длины $$$n$$$, состоящая из строчных латинских букв, а также целое число $$$k$$$. За один шаг вы можете выполнить одну любую операцию из следующих двух:
Вы можете сделать произвольное (возможно, нулевое) число шагов. Найдите лексикографически наименьшую строку, которую можно получить после какого-либо числа шагов.
Строка $$$a$$$ лексикографически меньше строки $$$b$$$ такой же длины, если выполняется следующее:
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k < n \le 10^5$$$).
Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$, состоящую из строчных латинских букв.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите лексикографически наименьшую строку, которую можно получить после какого-либо (возможно, нулевого) числа шагов.
54 2nima5 3panda9 2theforces7 3amirfar6 4rounds
aimn aandp ceefhorst aafmirr dnorsu
В первом наборе входных данных можно получить строку «aimn», выполняя следующие операции:
Можно доказать, что невозможно получить строку, лексикографически меньшую, чем «aimn». Значит, «aimn» и является ответом.
Во втором наборе входных данных можно получить строку «aandp», выполняя следующие операции:
Можно доказать, что невозможно получить строку, лексикографически меньшую, чем «aandp». Значит, «aandp» и является ответом.
Название |
---|