SP8550 LSQF - Longest Square Factor

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.

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 $ ^{5} $ .

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.