Дана строка \(s\) из строчных букв английского алфавита и число \(k\). Назовем строку из строчных букв английского алфавита красивой, если количество вхождений каждой буквы в эту строку кратно числу \(k\). Требуется найти лексикографически минимальную красивую строку длины \(n\), которая лексикографически больше или равна строке \(s\). Если такой строки не существует, выведите \(-1\).
Строка \(a\) лексикографически меньше строки \(b\), если и только если выполняется один из следующих пунктов:
- \(a\) — префикс \(b\), но \(a \ne b\);
- в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(b\).
Выходные данные
Для каждого тестового случая в отдельной строке выведите лексикографически минимальную красивую строку длины \(n\), которая больше или равна строке \(s\), или \(-1\), если такой строки не существует.
Примечание
В первом наборе входных данных «acac» лексикографически больше или равна \(s\), а каждая буква в ней встречается \(2\) или \(0\) раз, поэтому она красивая.
Во втором наборе входных данных каждая буква в \(s\) встречается \(0\) или \(1\) раз, поэтому сама \(s\) является ответом.
Можно показать, что в третьем наборе подходящей строки нет.
В четвертом примере каждая буква встречается \(0\), \(3\) или \(6\) раз в «abaabaaab». Все эти числа делятся на \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 2
abcd
3 1
abc
4 3
aaaa
9 3
abaabaaaa
|
acac
abc
-1
abaabaaab
|