Mikhail strikes back

Time limit5sMemory limit4 MB

Summary

Insert the fewest letters into a string of up to 15000 characters to make it a palindrome, then print the count and one resulting palindrome.

Level: Medium6 of 10
Topics: String, Dynamic programming, Divide and conquer
Solved: No attempts yet

Problem

Note the unusual memory limit in this problem.

Vasya loves taking part in informatics olympiads. He has realized that he enjoys string problems the most. Recently he was impressed by a newly invented data structure, the palindrome tree. It can find palindromes even where there are none.

Vasya wants the palindrome tree to create palindromes from strings instead of searching for them. He only wants to insert characters at arbitrary positions of a string. He does not want to delete or change any existing character, since he values the strings he is given. Help him find a way to turn a given string into a palindrome.

Input

The only line contains a non-empty string $s$ of lowercase English letters. Its length $|s|$ does not exceed $15\,000$ characters.

Output

On the first line, print $a$ , the minimum number of characters that must be added to $s$ to make it a palindrome. On the second line, print a string $t$ , a palindrome obtained from $s$ by adding exactly $a$ characters, so that $|s| + a = |t|$ .

Hint

A palindrome is a string that reads the same in both directions. For example, "a" and "abraarba" are palindromes, while "ab" and "abracadabra" are not.

Examples2

Example 1
Input
```
ab
```
Expected output
```
1
bab
```
Example 2
Input
```
abba
```
Expected output
```
0
abba
```