Problem E. Fibonacci level

Author:M. Sporyshev, A. Klenin, A. Baranov   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

For arbitrary non-empty strings S1 and S2, the Fibonacci sequence of strings is defined by a recurrence Si+2 = Si+1 + Si, where the '+' sign denotes string concatenation.

Let's say that string T has Fibonacci level n if there exists some Fibonacci sequence of strings which contains Sn = T. Note that any string of length 2 or more has Fibonacci level 3.

Your program must, given a string T, find its maximum Fibonacci level n as well as two starting strings S1 and S2 of corresponding Fibonacci sequence of strings.

Input file format

Input file contains a single string T, consisting of lowercase Latin letters.

Output file format

Output file must contain 3 lines: integer n followed by strings S1 and S2.

If there are several optimal solutions, output any of them.

Constraints

2 ≤ |T| ≤ 106

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
oxax
3
xax
o
2
cabccab
5
ab
c
3
axaxax
4
ax
ax

0.040s 0.007s 15