CF1493C K-beautiful Strings

给定一个只包含小写英文字母的字符串 $s$ 和一个整数 $k$。我们称一个只包含小写英文字母的字符串为“美丽的”，当且仅当该字符串中每个字母出现的次数都能被 $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$。

在第一个测试用例中，"acac" 字典序大于等于 $s$，并且每个字母出现 $2$ 次或 $0$ 次，因此它是美丽的。 在第二个测试用例中，$s$ 中每个字母出现 $0$ 次或 $1$ 次，因此 $s$ 本身就是答案。 可以证明第三个测试用例不存在符合条件的字符串。 在第四个测试用例中，"abaabaaab" 中每个字母出现 $0$、$3$ 或 $6$ 次，这些数都能被 $3$ 整除。 由 ChatGPT 4.1 翻译