Муу#5491

Муу

1 секунда

128 мегабайтів

Легка

Корови підсіли на нову гру в слова, яку називають "Муу". У неї грають кілька корів, що стоять в лінію. Кожна корова повинна назвати одну певну букву якомога швидше. Корова, яка помилиться, вибуває з гри.

Послідовність букв у грі Муу нескінченна. Починається вона так:

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)$ — слово з $3$ літер m o o. Послідовність $S (k)$ виходить з копії послідовності $S (k - 1)$ S(k-1), слова m o ...o з $k + 2$ k+2 літерами $o$ , за якими йде ще одна копія послідовності $S (k - 1)$ S(k-1). Наприклад:

S (0) S (1) S (2) = m o o = m o o m o o o m o o = 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

\begin{align*} S(0) &= \textbf{m o o} \\ S(1) &= \textbf{m o o m o o o m o o} \\ S(2) &= \textbf{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} \\ \end{align*}

Можна помітити, що таким чином будується нескінченно довгий рядок, і саме він використовується в грі Муу. Бессі, мудра корова, хоче дізнатися про $n$ -у літеру цієї послідовності: якою вона буде — m чи o? Допоможіть їй дізнатися це!

Вхідні дані

Одне ціле число $n$ ( $1 \leq n \leq 1 0^{9}$ 1 \leq n \leq 10^9).

Вихідні дані

Одна літера — m або o.

Приклади

Приклад

Приклад 1

Примітка

У першому прикладі четверта літера — $m$ .

У другому прикладі шоста літера — $o$ .