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

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