C. K-красивые строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$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$$$, если такой строки не существует.

Пример
Входные данные
4
4 2
abcd
3 1
abc
4 3
aaaa
9 3
abaabaaaa
Выходные данные
acac
abc
-1
abaabaaab
Примечание

В первом наборе входных данных «acac» лексикографически больше или равна $$$s$$$, а каждая буква в ней встречается $$$2$$$ или $$$0$$$ раз, поэтому она красивая.

Во втором наборе входных данных каждая буква в $$$s$$$ встречается $$$0$$$ или $$$1$$$ раз, поэтому сама $$$s$$$ является ответом.

Можно показать, что в третьем наборе подходящей строки нет.

В четвертом примере каждая буква встречается $$$0$$$, $$$3$$$ или $$$6$$$ раз в «abaabaaab». Все эти числа делятся на $$$3$$$.