给定一个字符串 $$$s$$$,长度为 $$$n$$$,由小写拉丁字母组成。
您最多可以将字符串中的一个字符替换为任意小写拉丁字母。
打印可以从原始字符串中获得的按字典顺序排列的最小字符串,并且包含最大数量的回文作为子字符串。请注意,如果回文作为子字符串出现多次,则按其出现的次数进行计数。
当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:
- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 包含一个在字母表中出现早于 $$$b$$$ 中相应字母的字母。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) — 字符串中的字符数。
第二行包含字符串 $$$s$$$ 本身,由 $$$n$$$ 小写拉丁字母组成。
输出
在第一行中,打印一个整数——使用语句中描述的操作最多一次可以获得的回文子串的最大数量。
在第二行中,打印可以从 $$$s$$$ 获得的字符串,并且该字符串具有最大可能的回文子串数。如果有多个答案,请打印字典顺序最小的一个。
示例
输入 #1
5 aabaa
输出 #1
15 aaaaa
输入 #2
5 aaaaa
输出 #2
15 aaaaa
输入 #3
4 awoo
输出 #3
7 aooo