310957: CF1913F. Palindromic Problem

F. Palindromic Problemtime limit per test5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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$.

Input

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.

Output

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.

ExamplesInput

5
aabaa

Output

15
aaaaa

Input

5
aaaaa

Output

15
aaaaa

Input

4
awoo

Output

7
aooo

题目大意：
给定一个长度为n的小写拉丁字母字符串s。你最多可以替换字符串中的一个字符为任意小写拉丁字母。输出从原始字符串获得且包含最多回文子串的字典序最小的字符串。如果回文子串出现多次，则按出现次数计算。字符串a在字典序上小于字符串b，当且仅当以下条件之一成立：a是b的前缀但a不等于b；在a和b的第一个不同的位置上，a包含的字母在字母表中出现在b的相应字母之前。

输入输出数据格式：
输入：
第一行包含一个整数n（1≤n≤3×10^5）——字符串的字符数。
第二行包含恰好由n个小写拉丁字母组成的字符串s。

输出：
第一行，打印一个整数——使用题目描述中的操作最多一次可以获得的最大回文子串数。
第二行，打印从s获得的具有最大可能回文子串数的字符串。如果有多个答案，则输出字典序最小的。题目大意： 给定一个长度为n的小写拉丁字母字符串s。你最多可以替换字符串中的一个字符为任意小写拉丁字母。输出从原始字符串获得且包含最多回文子串的字典序最小的字符串。如果回文子串出现多次，则按出现次数计算。字符串a在字典序上小于字符串b，当且仅当以下条件之一成立：a是b的前缀但a不等于b；在a和b的第一个不同的位置上，a包含的字母在字母表中出现在b的相应字母之前。 输入输出数据格式： 输入： 第一行包含一个整数n（1≤n≤3×10^5）——字符串的字符数。 第二行包含恰好由n个小写拉丁字母组成的字符串s。 输出： 第一行，打印一个整数——使用题目描述中的操作最多一次可以获得的最大回文子串数。 第二行，打印从s获得的具有最大可能回文子串数的字符串。如果有多个答案，则输出字典序最小的。