Вам дана строка \(s\) длины \(n\), состоящая из строчных латинских букв.
Вам разрешено заменить не более одного символа строки на произвольную строчную латинскую букву.
Выведите лексикографически минимальную строку, которая получается из исходной и содержит максимальное количество палиндромов в качестве подстрок. Если какой-то палиндром входит как подстрока несколько раз, он учитывается столько же раз, сколько встречается в строке.
Строка \(a\) лексикографически меньше строки \(b\), если и только если выполняется один из следующих пунктов:
- \(a\) — префикс \(b\), но \(a \ne b\);
- в первой позиции, где \(a\) и \(b\) различаются, в строке \(a\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(b\).
Выходные данные
В первой строке выведите одно целое число — максимальное количество подстрок-палиндромов, которое может быть у строки, которую можно получить, применив операцию не более одного раза.
Во второй строке выведите строку, которую можно получить из \(s\) и которая содержит максимальное количество подстрок-палиндромов. Если таких строк несколько, выведите лексикографически минимальную.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
aabaa
|
15
aaaaa
|
|
2
|
5
aaaaa
|
15
aaaaa
|
|
3
|
4
awoo
|
7
aooo
|