Distribuição de Strings
Phoenix tem uma string $$s$$ composta por letras latinas minúsculas. Ele quer distribuir todas as letras da string em $$k$$ strings $$a_1, a_2, …, a_k$$, não vazias, tal que todas as letras da string $$s$$ sejam distribuidas. As strings $$a_i$$ não precisam ser substrings de $$s$$. Phoenix pode distruibuir as letras de $$s$$ e rearranjá-las do jeito que ele quiser em cada uma das strings $$a_i$$.
Por exemplo, se $$s = baba$$ e $$k = 2$$, Phoenix pode distribuir as letras da string de diversas maneiras, como:
- $$ba$$ e $$ba$$
- $$a$$ e $$abb$$
- $$ab$$ e $$ab$$
- $$aa$$ e $$bb$$
Mas essas maneiras de distribuição são inválidas:
- $$baa$$ e $$ba$$
- $$b$$ e $$ba$$
- $$baba$$ e uma string vazia ($$a_i$$ deve ser não vazia)
Phoenix deseja distribuir as letras da string $$s$$ em $$k$$ strings $$a_1, a_2, …, a_k$$ de modo a minimizar a string lexicograficamente máxima entre todas elas, ou seja, minimizar $$max(a_1, a_2, …, a_k)$$. Ajude-o a encontrar a distribuição ótima e imprima o menor valor possível de $$max(a_1, a_2, …, a_k)$$.
Uma string $$x$$ é lexicograficamente menor que uma string $$y$$ se $$x$$ é um prefixo de $$y$$ e $$x \neq y$$, ou existe algum índice $$i$$ tal que $$x_i < y_i$$ e para todo $$j, (1 \leq j < i)$$, $$x_j = y_j$$.
Entrada:
A entrada consiste em diversos casos de teste. A primeira linha contém um intero $$t$$, o número de casos de teste. Cada caso de teste possui duas linhas.
A primeira linha de cada caso de teste consiste em dois inteiros $$n$$ e $$k$$, o tamanho da string $$s$$ e o número de strings não vazias em que Phoenix quer distribuir as letras de $$s$$, respectivamente.
A segunda linha de cada caso de teste tem a string $$s$$ de tamanho $$n$$, que é formada por letras latinas minúsculas.
Saída
Imprima $$t$$ strings, a i-ésima deve ser o valor mínimo de $$max(a_1, a_2, …, a_k)$$ para o i-ésimo caso de teste.
Restrições:
- $$1 \leq k \leq n \leq 10^5$$
- $$1 \leq t \leq 10^3$$
Exemplos:
ENTRADA |
SAÍDA |
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 |