C. Феникс и распределение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Феникса есть строка $$$s$$$, состоящая из строчных букв латинского алфавита. Он хочет распределить все буквы своей строки по $$$k$$$ непустым строкам $$$a_1, a_2, \dots, a_k$$$ так, что каждая буква из $$$s$$$ попадет ровно в одну из строк $$$a_i$$$. Строки $$$a_i$$$ не обязаны быть подстроками $$$s$$$. Феникс может распределить буквы $$$s$$$ и переупорядочить их внутри каждой строки $$$a_i$$$ так как захочет.

Например, если $$$s = $$$ baba и $$$k=2$$$, Феникс может распределить буквы своей строки множеством способов, в том числе:

  • ba и ba
  • a и abb
  • ab и ab
  • bb и aa

Однако получить такие варианты он не может:

  • baa и ba
  • b и ba
  • baba и пустая строка ($$$a_i$$$ должны быть непустыми)

Феникс хочет разделить свою строку $$$s$$$ на $$$k$$$ строк $$$a_1, a_2, \dots, a_k$$$ так, чтобы минимизировать лексикографически максимальную строку среди них, т. е. минимизировать $$$max(a_1, a_2, \dots, a_k)$$$. Помогите ему найти оптимальное распределение и выведите минимально возможное значение $$$max(a_1, a_2, \dots, a_k)$$$.

Строка $$$x$$$ лексикографически меньше, чем строка $$$y$$$, если либо $$$x$$$ является префиксом $$$y$$$ (и $$$x \ne y$$$), либо существует такой индекс $$$i$$$ ($$$1 \le i \le min(|x|, |y|))$$$, что $$$x_i$$$ < $$$y_i$$$ и для всех $$$j$$$ $$$(1 \le j < i)$$$ $$$x_j = y_j$$$. Здесь $$$|x|$$$ обозначает длину строки $$$x$$$.

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

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

В первой строке каждого набора задано два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 10^5$$$)  — длина строки $$$s$$$ и количество не пустых строк, в которые Феникс хочет распределить буквы $$$s$$$, соответственно.

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

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

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

Выведите $$$t$$$ ответов — по одному на набор входных данных; $$$i$$$-й ответ — минимально возможный $$$max(a_1, a_2, \dots, a_k)$$$ в $$$i$$$-м наборе.

Пример
Входные данные
6
4 2
baba
5 2
baacb
5 3
baacb
5 3
aaaaa
6 4
aaxxzz
7 1
phoenix
Выходные данные
ab
abbc
b
aa
x
ehinopx
Примечание

В первом наборе входных данных, одно из оптимальных решений — разбить baba на ab и ab.

Во втором наборе входных данных, одно из оптимальных решений — разбить baacb на abbc и a.

В третьем наборе, одно из оптимальных решений — разбить baacb на ac, ab и b.

В четвертом наборе, одно из оптимальных решений — разбить aaaaa на aa, aa и a.

В пятом наборе, одно из оптимальных решений — разбить aaxxzz на az, az, x и x.

В шестом наборе, одно из оптимальных решений — разбить phoenix на ehinopx.