Вам дана строка $$$s$$$ длины $$$n$$$, состоящая из строчных латинских букв.

Вам разрешено заменить не более одного символа строки на произвольную строчную латинскую букву.

Выведите лексикографически минимальную строку, которая получается из исходной и содержит максимальное количество палиндромов в качестве подстрок. Если какой-то палиндром входит как подстрока несколько раз, он учитывается столько же раз, сколько встречается в строке.

Строка $$$a$$$ лексикографически меньше строки $$$b$$$, если и только если выполняется один из следующих пунктов:

• $$$a$$$ — префикс $$$b$$$, но $$$a \ne b$$$;
• в первой позиции, где $$$a$$$ и $$$b$$$ различаются, в строке $$$a$$$ находится буква, которая встречается в алфавите раньше, чем соответствующая буква в $$$b$$$.