Ela 非常喜欢读书,就像她在 DTL 的新同事一样!成为 DTL 工程师后的第一天,她面临同事的挑战,将一堆书分类到书架上的不同隔间中。
$$$n$$$ 书籍必须在书架上分成 $$$k$$$ 个隔间($$$n$$$ 可以被 $$$k$$$ 整除)。每本书都由从“a”到“y”的小写拉丁字母表示,这是书名的开头字母。
Ela 必须在每个隔间中准确堆放 $$$\frac{n}{k}$$$ 本书。书堆放好后,对于从 $$$1$$$ 到 $$$k$$$ 索引的每个隔间,她取出由代表该隔间中所有书籍的字母组成的多组字母中的最小排除 (MEX) 字母,然后将所得字母组合成一个字符串。生成的字符串的第一个字母是由第一个分隔符形成的字母多重集的 MEX 字母,生成的字符串的第二个字母是由第二个分隔符形成的字母多重集的 MEX 字母,...等等。请注意,在该问题的约束下,由于未使用“z”,因此始终可以确定该问题中找到的任何多重集的 MEX 字母。
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 可以找到的最优字符串。
示例
输入 #1
5 12 3 cabccadabaac 12 6 cabccadabaac 12 12 cabccadabaac 25 1 abcdefghijklmnopqrstuvwxy 10 5 bcdxedbcfg
输出 #1
edb ccbbba bbbbbaaaaaaa z aaaaa
注意
在第一个测试用例中,书籍可以分为 $$$3$$$ 隔间,如下所示:
- 第一个隔间包含索引为 $$$1, 2, 3, 7$$$ 的书籍: $$$multiset_1 = \{$$$'c', 'a', 'b', 'd'$$$\}$$$ $$$\rightarrow$$$ $$$MEX(multiset_1) =$$$ 'e'
- 第二个隔间包含索引为 $$$4, 5, 6, 9$$$ 的书籍:$$$multiset_2 = \{$$$'c', 'c', 'a', 'b'$$$\}$$$ $$$\rightarrow$$$ $$$MEX(multiset_2) =$$$ 'd'
- 第三个隔间包含剩余的书籍 $$$8, 10, 11, 12$$$ : $$$multiset_3 = \{$$$ 'a', 'a', 'a', 'c'$$$\}$$$ $$$\rightarrow$$$ $$$MEX(multiset_3) =$$$ 'b'
因此,答案是“edb”。可以证明,Ela 无法对书籍进行排序,从而产生按字典顺序排列的更大的字符串。