Moo 게임

Moo는 여러 사람이 함께 즐길 수 있는 게임으로, 각자 Moo 수열의 글자를 한 개씩 순서대로 외치면 된다.

Moo 수열은 길이가 무한한 문자열이며, 다음과 같이 시작한다.

m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o o

Moo 수열은 다음과 같이 재귀적으로 정의된다. 먼저 $S(0)$을 길이가 3인 문자열 moo라고 하자. $k \ge 1$인 모든 $k$에 대해, $S(k)$는 $S(k-1)$ 뒤에 문자 m 하나와 그 뒤에 오는 o $k+2$개로 이루어진 문자열(즉 m 다음에 o가 $k+2$개)을 붙이고, 다시 그 뒤에 $S(k-1)$을 붙여서 만든다.

S(0) = "m o o"
S(1) = "m o o m o o o m o o"
S(2) = "m o o m o o o m o o m o o o o m o o m o o o m o o"

이 과정을 반복하면 길이가 무한한 문자열을 얻을 수 있으며, 이 문자열을 Moo 수열이라고 한다.

정수 $N$이 주어졌을 때, Moo 수열의 $N$번째 글자를 구하는 프로그램을 작성하시오. (글자는 1번째부터 센다.)

첫째 줄에 정수 $N$ ($1 \le N \le 10^9$)이 주어진다.

Moo 수열의 $N$번째 글자(m 또는 o)를 출력한다.