Phoenix 有一个由小写拉丁字母组成的字符串 $$$s$$$。他想将字符串中的所有字母分配到 $$$k$$$ 非空字符串 $$$a_1, a_2, \dots, a_k$$$ 中,这样 $$$s$$$ 中的每个字母都恰好指向字符串 $$$a_i$$$ 之一。字符串 $$$a_i$$$ 不需要是 $$$s$$$ 的子字符串。 Phoenix 可以分配 $$$s$$$ 的字母,并根据需要重新排列每个字符串 $$$a_i$$$ 中的字母。
例如,如果 $$$s = $$$ baba 且 $$$k=2$$$,Phoenix 可能会以多种方式分配其字符串的字母,例如:
- ba和ba
- a 和 abb
- ab 和 ab
- aa 和 bb
但是这些方法无效:
- 咩咩咩
- b 和 ba
- baba 和空字符串($$$a_i$$$ 应该非空)
Phoenix 想要将字符串 $$$s$$$ 的字母分配到 $$$k$$$ 字符串 $$$a_1, a_2, \dots, a_k$$$ 中,以最小化其中按字典顺序排列的最大字符串,即。 e.最小化 $$$max(a_1, a_2, \dots, a_k)$$$。帮助他找到最佳分布并打印 $$$max(a_1, a_2, \dots, a_k)$$$ 的最小可能值。
如果 $$$x$$$ 是 $$$y$$$ 和 $$$x \ne y$$$ 的前缀,或者存在索引 $$$i$$$ ($$$1 \le i \le min(|x|, |y|))$$$ 使得 $$$x_i$$$ <,则字符串 $$$x$$$ 按字典顺序小于字符串 $$$y$$$ $$$y_i$$$ 并且对于每个 $$$j$$$ $$$(1 \le j < i)$$$ $$$x_j = y_j$$$。这里$$$|x|$$$表示字符串$$$x$$$的长度。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。每个测试用例由两行组成。
每个测试用例的第一行由两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 10^5$$$) 组成 - 字符串 $$$s$$$ 的长度和非空字符串的数量,Phoenix 分别希望将 $$$s$$$ 的字母分配到其中。
每个测试用例的第二行包含一个字符串 $$$s$$$,长度为 $$$n$$$,仅由小写拉丁字母组成。
保证所有测试用例的 $$$n$$$ 总和为 $$$\le 10^5$$$。
输出
打印 $$$t$$$ 答案 — 每个测试用例一个。第 $$$i$$$ 个答案应该是第 $$$i$$$ 个测试用例中 $$$max(a_1, a_2, \dots, a_k)$$$ 的最小可能值。
示例
输入 #1
6 4 2 baba 5 2 baacb 5 3 baacb 5 3 aaaaa 6 4 aaxxzz 7 1 phoenix
输出 #1
ab abbc b aa x ehinopx
注意
在第一个测试用例中,一个最佳解决方案是将 baba 分配给 ab 和 ab。
在第二个测试用例中,一个最佳解决方案是将 baacb 分配给 abbc 和 a。
在第三个测试用例中,一个最佳解决方案是将 baacb 分配为 ac、ab 和 b。
在第四个测试用例中,一个最佳解决方案是将aaaaa 分配为aa、aa 和a。
在第五个测试用例中,一个最佳解决方案是将 aaxxzz 分配为 az、az、x 和 x。
在第六个测试用例中,一个最佳解决方案是将phoenix分发到ehinopx中。