Коровы придумали новую игру “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
Эта последовательность проще всего описывается рекурсивно. Пусть S(0) будет последовательность из трех символов "m o o". S(k) получается конкатенацией: копии последовательности S(k-1), затем “m o … o” c k+2 символами ‘o’ и затем еще одна копия последовательности 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 – ‘m’ или ‘o’. Помогите ей!
PROBLEM NAME: moo
Формат входных данных
* Строка 1: Одно целое число N (1 <= N <= 10^9).
Формат выходных данных
* Строка 1: Единственная строка вывода должна содержать один символ, ‘m’ или ‘o’.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
11
|
m
|