Назовём строку сбалансированной, если все символы, которые в ней присутствуют, входят в неё одинаковое число раз. Например, «coder», «appall» и «ttttttt» — сбалансированные строки, а «wowwow» и «codeforces» — нет.
Вам дана строка \(s\) длины \(n\), состоящая из строчных латинских букв. Найдите сбалансированную строку \(t\) той же длины \(n\), состоящую из строчных латинских букв и отличающуюся от строки \(s\) в как можно меньшем числе позиций. Другими словами, число индексов \(i\) таких, что \(s_i \ne t_i\), должно быть минимальным возможным.
Выходные данные
Для каждого набора входных данных выведите наименьшее число позиций, в которых строка \(s\) и сбалансированная строка \(t\) могут отличаться, и далее выведите саму такую строку \(t\).
Если существует несколько решений, выведите любое из них. Можно показать, что хотя бы одна сбалансированная строка всегда существует.
Примечание
В первом наборе входных данных заданная строка «hello» не является сбалансированной: буквы «h», «e» и «o» встречаются в ней по одному разу, а буква «l» — два раза. С другой стороны, строка «helno» сбалансирована: в ней присутствуют пять разных букв, и каждая из них встречается ровно один раз. Строки «hello» и «helno» отличаются всего в одной позиции — в четвёртом символе. Возможны и другие решения.
Во втором наборе входных данных строка «codefofced» сбалансирована, так как в ней присутствуют только буквы «c», «o», «d», «e» и «f», и каждая из них встречается ровно два раза.
В третьем наборе входных данных строка «eeeee» сбалансирована, так как в ней присутствует только буква «e».
В четвёртом наборе входных данных заданная строка «appall» уже сбалансирована.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5
hello
10
codeforces
5
eevee
6
appall
|
1
helno
2
codefofced
1
eeeee
0
appall
|