問題文

以下のような漸化式を考えます。

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

解は複数ある場合もあることに注意してください。

Source Name

Code Formula 2014 本戦