Description

Cow Bessie has recently been studying string operations. She constructs new strings one by one using the following rules:

$S(0) =$ moo.

$S(1) = S(0) +$ m $+$ ooo $+ S(0) =$ moo $+$ m $+$ ooo $+$ moo $=$ moomooomoo.

$S(2) = S(1) +$ m $+$ oooo $+ S(1) =$ moomooomoo $+$ m $+$ oooo $+$ moomooomoo $=$ moomooomoomoooomoomooomoo.

$\dots$

Bessie keeps generating strings until the length of the last generated string is at least the input integer $N$.

From the above, we can see that the $k$-th string is formed by concatenating: the $(k-1)$-th string $+$ m $+$ $(k+2$ 个 $o) +$ the $(k-1)$-th string.

Now the problem is: given an integer $N$ ($1 \leq N \leq 10^9$), determine whether the $N$-th character is the letter m or o.

Input Format

A single positive integer $N$.

Output Format

A single character, m or o.

11

m

Hint

Sample explanation:

As stated, string $S(0)$ is moo. We need the $11$-th character, and clearly $S(0)$ is not long enough. Likewise, the length of $S(1)$ is $10$, still not enough. The length of $S(2)$ is $25$, which is enough. The $11$-th character of $S(2)$ is m, so the answer is m.

Constraints:

$1\leq N\leq 10^9$.

Translated by ChatGPT 5