Moo Game

Interview

Time limit1sMemory limit128 MB

Summary

Given N up to 1e9, report whether the N-th character of the recursively defined Moo sequence is 'm' or 'o'.

Level: Medium6 of 10
Topics: Recursion, Divide and conquer, Math, Implementation
Solved: No attempts yet

Problem

Moo is a game that several people can enjoy together: the players take turns shouting the characters of the Moo sequence, one character each, in order.

The Moo sequence is an infinite string that begins like this:

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

The Moo sequence is defined recursively. First, let $S(0)$ be the length-3 string moo. For every $k \ge 1$ , $S(k)$ is formed by taking $S(k-1)$ , then appending the string made of a single m followed by $k+2$ copies of o (that is, m followed by $k+2$ os), and then appending $S(k-1)$ again.

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"

Repeating this process yields an infinite string, which is called the Moo sequence.

Given an integer $N$ , write a program that finds the $N$ -th character of the Moo sequence (characters are counted starting from 1).

Input

The first line contains an integer $N$ ( $1 \le N \le 10^9$ ).

Output

Print the $N$ -th character of the Moo sequence (either m or o).

Examples4

Example 1
Input
```
11
```
Expected output
```
m
```
Example 2
Input
```
1
```
Expected output
```
m
```
Example 3
Input
```
3
```
Expected output
```
o
```
Example 4
Input
```
4
```
Expected output
```
m
```