Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

data structures

hashing

string suffix structures

strings

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Palindromic Problem

time limit per test

5 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou 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.

Examples

Input

5aabaa

Output

15 aaaaa

Input

5aaaaa

Output

15 aaaaa

Input

4awoo

Output

7 aooo

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/23/2024 08:59:31 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|