题目描述

Ela 非常喜欢阅读，就像她在 DTL 的新同事们一样！在成为 DTL 工程师的第一天，她被同事挑战，将一堆书分到书架上的不同隔间里。现在有 $n$ 本书需要被分到 $k$ 个隔间中（$n$ 能被 $k$ 整除）。每本书用一个小写拉丁字母 'a' 到 'y' 表示，该字母是书名的首字母。

Ela 必须在每个隔间中恰好放入 $\frac{n}{k}$ 本书。分好后，对于每个编号从 $1$ 到 $k$ 的隔间，她会取出该隔间所有书的字母组成的多重集的最小未出现字母（MEX），然后将这些字母依次组合成一个字符串。结果字符串的第一个字母是第一个隔间的 MEX，第二个字母是第二个隔间的 MEX，依此类推。请注意，在本题的约束下，所有多重集的 MEX 都一定存在，因为不会出现字母 'z'。

Ela 想知道，她能得到的字典序最大的结果字符串是什么？

如果满足以下任一条件，则字符串 $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$ 的字符串，表示 Ela 能得到的字典序最大的结果字符串。

说明/提示

在第一个测试用例中，书可以被分为 $3$ 个隔间，具体如下：

• 第一个隔间包含编号 $1, 2, 3, 7$ 的书：$multiset_1 = \{$ 'c', 'a', 'b', 'd' $\}$，$MEX(multiset_1) =$ 'e'
• 第二个隔间包含编号 $4, 5, 6, 9$ 的书：$multiset_2 = \{$ 'c', 'c', 'a', 'b' $\}$，$MEX(multiset_2) =$ 'd'
• 第三个隔间包含剩下的书 $8, 10, 11, 12$：$multiset_3 = \{$ 'a', 'a', 'a', 'c' $\}$，$MEX(multiset_3) =$ 'b'

因此，答案是 'edb'。可以证明，Ela 无法通过其他分配方式得到字典序更大的字符串。

由 ChatGPT 4.1 翻译

样例

5
12 3
cabccadabaac
12 6
cabccadabaac
12 12
cabccadabaac
25 1
abcdefghijklmnopqrstuvwxy
10 5
bcdxedbcfg

edb
ccbbba
bbbbbaaaaaaa
z
aaaaa