Palindrome

Interview

Time limit1sMemory limit1024 MB

Summary

Given a string of N uppercase letters, find the fewest replacements needed to make it a palindrome, and print the alphabetically smallest result.

Level: Easy3 of 10
Topics: String, Greedy
Solved: No attempts yet

Statement

Kevin earned full marks on the palindrome problem in the qualifying round of the informatics olympiad. His teacher saw this and gave him a harder problem about palindromes of varying lengths.

As with number sequences, a text is called a palindrome if it reads the same forwards and backwards. For example, ABBA is a palindrome because it reads ABBA backwards. ABCD is not a palindrome, since it reads DCBA backwards.

Write a program that finds the minimum number of letter replacements needed to turn a given text into a palindrome.

Input

The first line contains an integer $N$ ( $1 \le N \le 300$ ).

The second line contains a text of $N$ uppercase Latin letters (A ... Z).

Output

The first line prints the integer $K$ , the minimum number of letters that must be replaced to turn the given text into a palindrome.

The second line prints the resulting palindrome. If several palindromes can be made with the minimum number of replacements, print the alphabetically first one.

Examples2

Example 1
Input
```
4
ABBA
```
Expected output
```
0
ABBA
```
Example 2
Input
```
4
ABCC
```
Expected output
```
2
ABBA
```