CF1493C.K-beautiful Strings

You are given a string $s$ consisting of lowercase English letters and a number $k$. Let's call a string consisting of lowercase English letters beautiful if the number of occurrences of each letter in that string is divisible by $k$. You are asked to find the lexicographically smallest beautiful string of length $n$, which is lexicographically greater or equal to string $s$. If such a string does not exist, output $-1$.

A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds:

• $a$ is a prefix of $b$, but $a \ne b$;
• in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.

给你一个由小写英文字母组成的字符串 $s$ 和一个整数 $k$。我们称一个仅由小写英文字母组成的字符串为“优美的”，当且仅当其中每个字母的出现次数均能被 $k$ 整除。你需要找出长度为 $n$ 的字典序最小的优美字符串，且该字符串的字典序大于或等于字符串 $s$。如果不存在这样的字符串，则输出 $-1$。

字符串 $a$ 的字典序小于字符串 $b$，当且仅当满足以下条件之一：

• $a$ 是 $b$ 的前缀，但 $a \ne b$；
• 在 $a$ 与 $b$ 首次出现不同字符的位置上，$a$ 中的该字符在字母表中位于 $b$ 中对应字符之前。

The first line contains a single integer $T$ ($1 \le T \le 10\,000$) — the number of test cases.

The next $2 \cdot T$ lines contain the description of test cases. The description of each test case consists of two lines.

The first line of the description contains two integers $n$ and $k$ ($1 \le k \le n \le 10^5$) — the length of string $s$ and number $k$ respectively.

The second line contains string $s$ consisting of lowercase English letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

第一行包含一个整数 $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$。

For each test case output in a separate line lexicographically smallest beautiful string of length $n$, which is greater or equal to string $s$, or $-1$ if such a string does not exist.

对于每个测试用例，在单独一行中输出长度为 $n$ 的字典序最小的优美字符串，该字符串大于或等于字符串 $s$；如果不存在这样的字符串，则输出 $-1$。

In the first test case "acac" is greater than or equal to $s$, and each letter appears $2$ or $0$ times in it, so it is beautiful.

In the second test case each letter appears $0$ or $1$ times in $s$, so $s$ itself is the answer.

We can show that there is no suitable string in the third test case.

In the fourth test case each letter appears $0$, $3$, or $6$ times in "abaabaaab". All these integers are divisible by $3$.

在第一个测试用例中，“acac”大于或等于 $s$，且其中每个字母出现 $2$ 次或 $0$ 次，因此它是优美的。

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

我们可以证明：第三个测试用例中不存在满足条件的字符串。

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