Codeforces Round 705 (Div. 2) |
---|
Finished |
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:
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.
4 4 2 abcd 3 1 abc 4 3 aaaa 9 3 abaabaaaa
acac abc -1 abaabaaab
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$$$.
Name |
---|