Крюк Мауи опять сломался. В этот раз он далековато от Те Фити, чтобы та помогла ему его починить. Однако он знает одно заклинание, которое может ему помочь (не зря же он полубог).
Это заклинание он всегда носит с собой — оно написано на небольшом клочке его одежды. Но теперь он жалеет, что у него нет тату с этим заклинанием — за время плаваний надпись размыло, и некоторые буквы стали менее узнаваемы. Мауи попытался разобрать их, и в итоге получил строку $$$s$$$, но что-то не сходится.
Он точно помнит, что в верном заклинании нет подстрок, являющихся палиндромами, то есть читающихся одинаково слева направо и справа налево. Также он уверен, что получившаяся у него строка $$$s$$$ не сильно отличается от изначального заклинания.
Помогите ему определить минимальное число букв, которое необходимо заменить в $$$s$$$, чтобы в ней не осталось подстрок-палиндромов. Напомним, что подстрока — это (в данном случае, непустая) последовательность подряд идущих символов строки.
В первой строке дано целое число $$$n$$$ — длина строки $$$s$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).
Далее дана сама строка $$$s$$$ из $$$n$$$ маленьких латинских букв (от 'a' до 'z') — заклинание, в котором, возможно, какие-то буквы Мауи разобрал неправильно.
В первой строке выведите целое число $$$k$$$ — минимальное число необходимых замен.
Затем во второй строке выведите строку $$$s'$$$ из букв от 'a' до 'z', отличающуюся от $$$s$$$ ровно в $$$k$$$ буквах и не имеющую подстрок-палиндромов.
7abacaba
2 abzcyba
10aaaaaaaaaa
6 abcabcabca