CF1737A.Ela Sorting Books

Ela loves reading a lot, just like her new co-workers in DTL! On her first day after becoming an engineer in DTL, she is challenged by a co-worker to sort a heap of books into different compartments on the shelf.

$n$ books must be split into $k$ compartments on the bookshelf ($n$ is divisible by $k$). Each book is represented by a lowercase Latin letter from 'a' to 'y' inclusively, which is the beginning letter in the title of the book.

Ela must stack exactly $\frac{n}{k}$ books in each compartment. After the books are stacked, for each compartment indexed from $1$ to $k$, she takes the minimum excluded (MEX) letter of the multiset of letters formed by letters representing all books in that compartment, then combines the resulting letters into a string. The first letter of the resulting string is the MEX letter of the multiset of letters formed by the first compartment, the second letter of the resulting string is the MEX letter of the multiset of letters formed by the second compartment, ... and so on. Please note, under the constraint of this problem, MEX letter can always be determined for any multiset found in this problem because 'z' is not used.

What is the lexicographically greatest resulting string possible that Ela can create?

A string $a$ is lexicographically greater than a string $b$ if and only if one of the following holds:

• $b$ is a prefix of $a$, but $b \ne a$;
• in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears later in the alphabet than the corresponding letter in $b$.

The minimum excluded (MEX) letter of a multiset of letters is the letter that appears earliest in the alphabet and is not contained in the multiset. For example, if a multiset of letters contains $7$ letters 'b', 'a', 'b', 'c', 'e', 'c', 'f' respectively, then the MEX letter of this compartment is 'd', because 'd' is not included in the multiset, and all letters comes before 'd' in the alphabet, namely 'a', 'b' and 'c', are included in the multiset.

Ela 非常热爱阅读，就像她在 DTL 的新同事们一样！在成为 DTL 工程师的第一天，她就受到一位同事的挑战：将一堆书分类整理到书架上的不同隔间中。

共有 $n$ 本书需被分配到书架上的 $k$ 个隔间中（$n$ 可被 $k$ 整除）。每本书用一个小写拉丁字母 'a' 到 'y'（含端点）表示，该字母即为该书标题的首字母。

Ela 必须在每个隔间中恰好堆放 $\frac{n}{k}$ 本书。完成堆放后，对从 $1$ 到 $k$ 编号的每个隔间，她计算该隔间内所有书籍对应字母所构成多重集的最小未出现字母（MEX letter），再将这些 MEX 字母按隔间编号顺序拼接成一个字符串。即：结果字符串的第一个字母是第一个隔间的多重集的 MEX 字母，第二个字母是第二个隔间的多重集的 MEX 字母，依此类推。注意：根据本题约束条件，任意出现在本题中的多重集均能唯一确定其 MEX 字母，因为字母 'z' 不会被使用。

Ela 能构造出的字典序最大的结果字符串是什么？

字符串 $a$ 的字典序严格大于字符串 $b$，当且仅当满足以下任一条件：

• $b$ 是 $a$ 的前缀，但 $b \ne a$；
• 在 $a$ 与 $b$ 首次出现差异的位置上，$a$ 中的字母在字母表中位于 $b$ 中对应字母之后。

一个字母多重集的最小未出现字母（MEX letter），是指在字母表中最先出现且未包含于该多重集中的字母。例如，若某多重集包含字母 'b', 'a', 'b', 'c', 'e', 'c', 'f'（共 7 个字母），则该隔间的 MEX 字母为 'd'，因为 'd' 未出现在该多重集中，而所有在字母表中位于 'd' 之前的字母（即 'a', 'b', 'c'）均已包含在该多重集中。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 200$; $1 \le k \le n$). It is guaranteed that $n$ is divisible by $k$.

The second line of each test case contains a string of $n$ lowercase Latin letters from 'a' to 'y' inclusively. Each letter represents the starting letter of the title of a book in the initial heap.

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output a string of $k$ letters which is the most optimal string that Ela can find.

对于每个测试用例，输出一个由 $k$ 个字母组成的字符串，该字符串是 Ela 能找到的最优字符串。

In the first test case, the books can be divided into $3$ compartments as below:

• the first compartment contains the books with indices $1, 2, 3, 7$: multiset_1 = {'c', 'a', 'b', 'd'} $\rightarrow$ $MEX(multiset_1) =$ 'e'
• the second compartment contains the books with indices $4, 5, 6, 9$ : multiset_2 = {'c', 'c', 'a', 'b'} $\rightarrow$ $MEX(multiset_2) =$ 'd'
• the third compartment contains the remaining books $8, 10, 11, 12$ : multiset_3 = { 'a', 'a', 'a', 'c'} $\rightarrow$ $MEX(multiset_3) =$ 'b'

Therefore, the answer is 'edb'. It can be proven that there is no way that Ela can arrange the books so that it results in a lexicographically greater string.

在第一个测试用例中，这些书可以被划分为 $3$ 个隔间，如下所示：

• 第一个隔间包含索引为 $1, 2, 3, 7$ 的书：$multiset_1 = \{ \text{'c'}, \text{'a'}, \text{'b'}, \text{'d'} \}$ $\rightarrow$ $MEX(multiset_1) =$ 'e'
• 第二个隔间包含索引为 $4, 5, 6, 9$ 的书：$multiset_2 = \{ \text{'c'}, \text{'c'}, \text{'a'}, \text{'b'} \}$ $\rightarrow$ $MEX(multiset_2) =$ 'd'
• 第三个隔间包含剩余的书（索引为 $8, 10, 11, 12$）：$multiset_3 = \{ \text{'a'}, \text{'a'}, \text{'a'}, \text{'c'} \}$ $\rightarrow$ $MEX(multiset_3) =$ 'b'

因此，答案为 'edb'。可以证明，Ela 无法以任何其他方式排列这些书，从而得到字典序更大的字符串。