13022 - Moo

奶牛 Bessie 正在学习字符串操作，它按如下规则构造字符串：

• S(0) = \text{moo}
• 对于 k \ge 1 ， S(k) = S(k-1) + \text{m} + \underbrace{\text{oo}\cdots\text{o}}_{k+2\text{ 个 o}} + S(k-1)

例如：

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

即：第 k 个字符串由第 k-1 个字符串、一个字母 m、接着 k+2 个字母 o，再接着第 k-1 个字符串拼接而成。

现在给定 N ，请输出最终字符串中第 N 个字符是 m 还是 o。

输入只有一行，包含一个整数 N （ 1 \le N \le 10^9 ）。

输出一个字符，m 或 o。

样例说明

• S(0) = \text{moo} ，长度为 3，不足以包含第 11 个字符。
• S(1) = \text{moo} + \text{m} + \text{ooo} + \text{moo} = \text{moomooomoo} ，长度为 10，仍不够。
• S(2) = S(1) + \text{m} + \text{oooo} + S(1) ，长度为 10 + 1 + 4 + 10 = 25 ，足够大。
• 第 11 个字符位于 S(2) 的中间部分（因为前 10 个是 S(1) ），中间部分是 moooo，第 1 个字符是 m，因此输出 m。

数据范围与约定

• 1 \le N \le 10^9

USACO