Informática - Nivel Iniciante - Semana 4

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

Use esse link para submeter a sua solução.