Given a string x, the string obtained by concatenating x to itself is sometimes called the square of x.

Given a string s, output the longest string x such that its square is a substring of s. If you find more than one solution, output the lexicographically smallest.

Input

The first and only line of input contains a string s (consisting only of lowercase letters of the English alphabet). The length of s is less than or equal to 10⁵.

Output

To the first line of output print the length of the string x.
To the second line print the string x.

Such a string will always exist in the test data.

Example

Input:
abcabc

Output:
3
abc