Palindromic Problem

给你一个长为 $n$，由小写字母组成的字符串。你可以将至多一个字母替换为任意小写字母，使得这样操作之后字符串中的回文子串数量最多。 第一行输出操作后最多的回文子串数量。 第二行输出操作后的字符串。 如果有多个字符串满足要求，输出字典序最小的那个。

You are given a string $ s $ of length $ n $ , consisting of lowercase Latin letters. You are allowed to replace at most one character in the string with an arbitrary lowercase Latin letter. Print the lexicographically minimal string that can be obtained from the original string and contains the maximum number of palindromes as substrings. Note that if a palindrome appears more than once as a substring, it is counted the same number of times it appears. The string $ a $ is lexicographically smaller than the string $ b $ if and only if one of the following holds: - $ a $ is a prefix of $ b $ , but $ a \ne b $ ; - in the first position where $ a $ and $ b $ are different, the string $ a $ contains a letter that appears earlier in the alphabet than the corresponding letter in $ b $ .

The first line contains one integer $ n $ ( $ 1 \leq n \leq 3 \cdot 10^5 $ ) — the number of characters in the string. The second line contains the string $ s $ itself, consisting of exactly $ n $ lowercase Latin letters.

In the first line, print one integer — the maximum number of palindromic substrings that can be obtained using the operation described in the statement at most once. In the second line, print the string that can be obtained from $ s $ and has the maximum possible number of palindromic substrings. If there are multiple answers, print the lexicographically smallest one.

5
aabaa

15
aaaaa

5
aaaaa

15
aaaaa

4
awoo

7
aooo