Problem D. 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.

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