問題文
考虑以下递归公式。 当
- F_{1,0} =
b - F_{2,0} =
a - n≧3 和 0≦k<2^{n-2} 和 k 为偶数时, 当F_{n,k} = F_{n-1,floor(k/2)} + F_{n-2,floor(k/4)}
- n≧3 和 0≦k<2^{n-2} 和 k 为奇数时,F_{n,k} = F_{n-2,floor(k/4)} + F_{n-1,floor(k/2)}
未由上述递推公式定义 F_{n,k} 不予考虑。 给出了
文字列 S 。这个字符串是 我们知道可以用F_{p,q} 的形式来表示。
S = F_{p,q} 变为 p,q ,1 请输出一个。
但是,floor(n) 是 与n 的下取整函数。
入力
输入是按以下格式从标准输入给出的。
S
- 1 字符串 S (1 ≦ |S| ≦ 20000) 。
出力
S = F_{p,q} 变为 p,q ,1 输出两者,以空格分隔。在输出末尾添加换行符。
入力例1
babaa
出力例1
5 5
- F_{1,0} =
b - F_{2,0} =
a - F_{3,1} = F_{1,0} + F_{2,0} =
ba - F_{4,2} = F_{3,1} + F_{2,0} =
baa - F_{5,5} = F_{3,1} + F_{4,2} =
babaa
,所以p=5, q=5 是您正在寻找的答案。 1 会有一个。
入力例2
aababaabaababaabaababaababaabaabab
出力例2
9 44
请注意,可能有多个解决方案。