P1885 Moo

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`.

A single positive integer $N$.

A single character, `m` or `o`.

**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