B. Обмен и разворот
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$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$$$).

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$, состоящую из строчных латинских букв.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите лексикографически наименьшую строку, которую можно получить после какого-либо (возможно, нулевого) числа шагов.

Пример
Входные данные
5
4 2
nima
5 3
panda
9 2
theforces
7 3
amirfar
6 4
rounds
Выходные данные
aimn
aandp
ceefhorst
aafmirr
dnorsu
Примечание

В первом наборе входных данных можно получить строку «aimn», выполняя следующие операции:

  1. Развернуть отрезок $$$[3,4]$$$. Строка превратится в «niam».
  2. Поменять местами $$$s_1$$$ и $$$s_3$$$. Строка превратится в «ainm».
  3. Развернуть отрезок $$$[3,4]$$$. Строка превратится в «aimn».

Можно доказать, что невозможно получить строку, лексикографически меньшую, чем «aimn». Значит, «aimn» и является ответом.

Во втором наборе входных данных можно получить строку «aandp», выполняя следующие операции:

  1. Поменять местами $$$s_3$$$ и $$$s_5$$$. Строка превратится в «paadn».
  2. Поменять местами $$$s_1$$$ и $$$s_3$$$. Строка превратится в «aapdn».
  3. Поменять местами $$$s_3$$$ и $$$s_5$$$. Строка превратится в «aandp».

Можно доказать, что невозможно получить строку, лексикографически меньшую, чем «aandp». Значит, «aandp» и является ответом.