问题描述

考虑以下递归式。

• $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$。

其中，$floor(n)$ 表示 $n$ 的底函数。

输入

输入从标准输入中获取，具有以下格式。

$S$

• 第1行是一个字符串 $S (1 ≦ |S| ≦ 20000)$。

输出

输出满足 $S = F_{p,q}$ 的其中一个 $p,q$，用空格分隔。输出末尾包含换行符。

示例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$ 是其中一个满足条件的答案。

示例2

aababaabaababaabaababaababaabaabab

输出示例2

9 44

请注意，答案可能有多个。

来源

Code Formula 2014 本赛