← 返回题目列表

Codeforces · 1348/C

C. 凤凰城和分销

中文机器翻译题面 查看原题

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中。