Symmetric String

Interview

Time limit1sMemory limit1024 MB

Summary

Given a string, find the fewest characters to append to its end so that it becomes a palindrome, and print those characters.

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

Problem

A string is symmetric if it reads the same from left to right and from right to left. For example, the following strings are symmetric:

123454321

abssddfddssba.

Gosho and Pesho play an interesting game. They write a string and try to make it symmetric by appending as few characters as possible to its end.

Write a program symmetric that reads the length N and the N characters of the string. It prints the minimum number of characters that must be appended to the end of the string to make it symmetric, followed by those characters.

Input

The first line contains N, the number of characters in the string. The second line contains the N characters of the string.

Output

The first line prints M, the minimum number of characters to append. The second line prints the M characters to append to the end of the string. If the string is already symmetric, the second line is not printed.

Constraints

$1 \le N \le 1050$

Examples3

Example 1
Input
```
7
alabala
```
Expected output
```
0
```
Example 2
Input
```
4
repe
```
Expected output
```
1
r
```
Example 3
Input
```
7
alpha21
```
Expected output
```
6
2ahpla
```