#P1885. Moo

Moo

题目描述

奶牛 Bessie 最近在学习字符串操作,它用如下的规则逐一的构造出新的字符串:

S(0)=S(0) = moo

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

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

\dots

Bessie 就这样产生字符串,直到最后产生的那个字符串长度不小于读入的整数 NN 才停止。

通过上面观察,可以发现第 kk 个字符串是由:第 k1k-1 个字符串 ++ m ++ (k+2(k+2o)+o) +k1k-1 个字符串连接起来的。

现在的问题是:给出一个整数 N(1N109)N (1 \leq N \leq 10^9),问第 NN 个字符是字母 m 还是 o

输入格式

一个正整数 NN

输出格式

一个字符,m 或者 o

11
m

提示

样例解释:

由题目所知:字符串 S(0)S(0)moo, 现在要求第 1111 个字符,显然字符串 S(0)S(0) 不够长;

同样 S(1)S(1) 的长度是 1010,也不够长;S(2)S(2) 的长度是 2525,够长了,S(2)S(2) 的第 1111 个字符是 m,所以答案就输出 m