A14100. 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$ .

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$ .

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.

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$ .