← 返回题目列表

Codeforces · 1493/C

C. K-美丽的琴弦

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

给你一个由小写英文字母和数字$$$k$$$组成的字符串$$$s$$$。如果由小写英文字母组成的字符串中每个字母出现的次数可以被 $$$k$$$ 整除,那么我们称该字符串为“漂亮”字符串。要求您找到长度为 $$$n$$$ 的字典顺序最小的漂亮字符串,该字符串按字典顺序大于或等于字符串 $$$s$$$。如果这样的字符串不存在,则输出$$$-1$$$。

当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:

- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中的某个字母比 $$$b$$$ 中的相应字母更早出现。

输入

第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 10\,000$$$) — 测试用例的数量。

接下来的 $$$2 \cdot T$$$ 行包含测试用例的描述。每个测试用例的描述由两行组成。

描述的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 10^5$$$) — 分别是字符串 $$$s$$$ 和数字 $$$k$$$ 的长度。

第二行包含由小写英文字母组成的字符串$$$s$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,在单独的行中输出按字典顺序排列的长度为 $$$n$$$ 的最小漂亮字符串,该字符串大于或等于字符串 $$$s$$$,或者 $$$-1$$$(如果这样的字符串不存在)。

示例

输入 #1

4
4 2
abcd
3 1
abc
4 3
aaaa
9 3
abaabaaaa

输出 #1

acac
abc
-1
abaabaaab

注意

第一个测试用例中“acac”大于或等于$$$s$$$,并且每个字母在其中出现$$$2$$$或$$$0$$$次,所以很漂亮。

在第二个测试用例中,每个字母在 $$$s$$$ 中出现 $$$0$$$ 或 $$$1$$$ 次,因此 $$$s$$$ 本身就是答案。

我们可以证明第三个测试用例中没有合适的字符串。

在第四个测试用例中,每个字母在“abaabaaab”中出现 $$$0$$$、$$$3$$$ 或 $$$6$$$ 次。所有这些整数都可以被$$$3$$$整除。