A. Эла распределяет книги
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Эла очень любит читать, как и ее новые коллеги по DTL! В первый же день её работы в DTL коллега попросил её распределить книги по отсекам на книжной полке.

$$$n$$$ книг должны быть распределены по $$$k$$$ отсекам на книжной полке ($$$n$$$ нацело делится на $$$k$$$). Каждой книге можно сопоставить одну строчную латинскую букву от 'a' до 'y' включительно, которая является начальной буквой в названии книги.

Эла должна положить ровно $$$\frac{n}{k}$$$ книг в каждый отсек. Отсеки пронумерованы от $$$1$$$ до $$$k$$$. Положив книги, для каждого отсека она возьмет ровно одну букву — MEX мультимножества букв, соответствующих книгам в этом отсеке, и затем объединит полученные буквы в одну строку. Первая буква итоговой строки — это буква MEX мультимножества букв в первом отсеке, вторая буква итоговой строки — это буква MEX мультимножества букв во втором отсеке, и так далее. Обратите внимание, что в ограничениях этой задачи MEX всегда может быть определен для любого мультимножества букв, соответствующих книгам, потому что 'z' не может являться начальной буквой в названиях книг.

Какую лексикографически наибольшую результирующую строку может получить Эла?

Строка $$$a$$$ лексикографически больше строки $$$b$$$ тогда и только тогда, когда выполняется одно из следующих условий:

  • $$$b$$$ является префиксом $$$a$$$, но $$$b \ne a$$$;
  • в первой позиции, где $$$a$$$ и $$$b$$$ различаются, в строке $$$a$$$ стоит буква, которая представлена в алфавите позже, чем соответствующая буква в $$$b$$$.

MEX мультимножества букв – это первая в алфавите буква, которая не входит в это мультимножество. Например, если мультимножество букв содержит $$$7$$$ букв 'b', 'a', 'b', 'c', 'e', 'c', 'f', то MEX этого мультимножества будет 'd', поскольку 'd' не содержится в мультимножестве, и все буквы, предшествующие 'd' в алфавите, а именно 'a', 'b' и 'c', содержатся в мультимножестве.

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

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$)  — количество наборов входных данных. Далее следуют наборы входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 200$$$; $$$1 \le k \le n$$$). Гарантируется, что $$$n$$$ нацело делится на $$$k$$$.

Вторая строка каждого набора входных данных содержит строку из $$$n$$$ строчных латинских букв от 'a' до 'y' включительно. Каждая буква представляет начальную букву названия очередной книги.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$1000$$$.

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

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

Пример
Входные данные
5
12 3
cabccadabaac
12 6
cabccadabaac
12 12
cabccadabaac
25 1
abcdefghijklmnopqrstuvwxy
10 5
bcdxedbcfg
Выходные данные
edb
ccbbba
bbbbbaaaaaaa
z
aaaaa
Примечание

В первом наборе входных данных книги можно распределить по $$$3$$$ отсекам как показано ниже:

  • в первом отсеке находятся книги с индексами $$$1, 2, 3, 7$$$: $$$multiset_1 = \{$$$'c', 'a', 'b', 'd'$$$\}$$$ $$$\rightarrow$$$ $$$MEX(multiset_1) =$$$ 'e'
  • во втором отсеке находятся книги с индексами $$$4, 5, 6, 9$$$ : $$$multiset_2 = \{$$$'c', 'c', 'a', 'b'$$$\}$$$ $$$\rightarrow$$$ $$$MEX(multiset_2) =$$$ 'd'
  • в третьем отсеке находятся книги с индексами $$$8, 10, 11, 12$$$: $$$multiset_3 = \{$$$'a', 'a' , 'a', 'c'$$$\}$$$ $$$\rightarrow$$$ $$$MEX(multiset_3) =$$$ 'b'

Следовательно, ответ 'edb'. Можно доказать, что Эла никак не может расположить книги так, чтобы в результате получилась лексикографически большая строка.