G. Che Forest
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка $$$s$$$ длины $$$n$$$. Вы выполняете следующие операции $$$k$$$ раз:

  • выбрать символ $$$s_i$$$ ($$$1 \le i \le n$$$) и переместить его в начало строки.
  • выбрать символ $$$s_i$$$ ($$$1 \le i \le n$$$) и переместить его в конец строки.
  • выбрать символ $$$s_i$$$ ($$$1 \le i \le n$$$) и переместить его в начало строки.
  • и так далее, в зависимости от четности номера операции.

Найдите лексикографически минимальную строку, которую вы можете получить.

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

Первая строка входных данных содержит единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$).

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

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
4
7 3
abacaba
9 2
theforces
5 4
edcba
7 3
pavlekn
Выходные данные
aaaacbb
cheforest
abcde
aeplknv
Примечание

В первом примере, мы можем проделать следующие операции:

  • $$$abac\color{red}{a}ba$$$ $$$\rightarrow$$$ $$$\color{red}{a}abacba$$$
  • $$$aa\color{red}{b}acba$$$ $$$\rightarrow$$$ $$$aaacba\color{red}{b}$$$
  • $$$aaacb\color{red}{a}b$$$ $$$\rightarrow$$$ $$$\color{red}{a}aaacbb$$$

Во втором примере, мы можем проделать следующие операции:

  • $$$thefor\color{red}{c}es$$$ $$$\rightarrow$$$ $$$\color{red}{c}thefores$$$
  • $$$c\color{red}{t}hefores$$$ $$$\rightarrow$$$ $$$chefores\color{red}{t}$$$