Problem Description

Consider the following recurrence relation:

• $F_{1,0}\ =$ b
• $F_{2,0}\ =$ a
• For $ n≧3 $ and $ 0≦k $ where $ k $ is even, $F_{n,k}\ =\ F_{n-1,floor(k/2)}\ +\ F_{n-2,floor(k/4)}$
• For $ n≧3 $ and $ 0≦k $ where $ k $ is odd, $F_{n,k}\ =\ F_{n-2,floor(k/4)}\ +\ F_{n-1,floor(k/2)}$

For $ F_{n,k} $ not defined by the above recurrence relation, it is not considered.

A string $ S $ is given, which is known to be representable in the form $ F_{p,q} $.

Output one pair of $ p,q $ such that $S\ =\ F_{p,q}$.

Here, $ floor(n) $ denotes the floor function of $ n $.

Input Format

The input is given from the standard input in the following format:

$ S $

• The first line contains the string $S\ (1\ ≦\ |S|\ ≦\ 20000)$.

Output Format

Output one pair of $ p,q $ such that $S\ =\ F_{p,q}$, separated by a space. End the output with a newline.

Sample Input and Output

Sample Input #1

babaa

Sample Output #1

5 5

Sample Input #2

aababaabaababaabaababaababaabaabab

Sample Output #2

9 44

Notes/Hints

Sample Explanation 1

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

Thus, $ p=5 $, $ q=5 $ is one of the solutions.

Sample Explanation 2

Note that there may be multiple solutions.

见题面 Input 部分

见题面 Output 部分