|Author:||M. Sporyshev, A. Klenin, A. Baranov||Time limit:||1 sec|
|Input file:||input.txt||Memory limit:||256 Mb|
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 contains a single string T, consisting of lowercase Latin letters.
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
|No.||Input file (
||Output file (|