問題文

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

• 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 の床関数とします。

入力例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

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