LSQF - Longest Square Factor

no tags 

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 105.

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

hide comments
Shaka Shadows: 2011-08-22 15:30:39

Really nice problem!!! Thanks Gustav :)

gustav: 2011-08-22 15:30:39

Seems fine now :D

Oleg: 2011-08-22 15:30:39

Nice try

gustav: 2011-08-22 15:30:39

You asked for it :)

Oleg: 2011-08-22 15:30:39

Try again :)

gustav: 2011-08-22 15:30:39

Ok, so just a little note here: I might throw in a few new test cases every now and then so if your solution isn't correct - your AC won't last forever :)

Last edit: 2011-03-15 15:48:27

Added by:gustav
Date:2011-03-13
Time limit:0.672s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem