Một đàn bò xếp thành hàng dài chơi trò "Moo": con bò thứ \(i\) phải hô đúng chữ cái ở vị trí thứ \(i\) của một dãy chữ vô hạn. Dãy này được xây dựng từ các xâu \(S(0), S(1), S(2), \dots\) như sau:
- \(S(0) = \texttt{moo}\);
- \(S(k)\) là ghép của ba phần theo thứ tự: xâu \(S(k-1)\), tiếp theo là chữ
mcùng \(k+2\) chữo, rồi lại xâu \(S(k-1)\).
Ví dụ:
- \(S(0) = \texttt{moo}\)
- \(S(1) = \texttt{moo}\;\texttt{mooo}\;\texttt{moo} = \texttt{moomooomoo}\)
- \(S(2) = \texttt{moomooomoo}\;\texttt{moooo}\;\texttt{moomooomoo}\)
Vì \(S(k-1)\) là phần đầu của \(S(k)\) nên dãy vô hạn là giới hạn của các xâu \(S(k)\) khi \(k\) tăng. Hãy cho biết chữ cái ở vị trí thứ \(N\) (đánh số từ 1) là m hay o.
Input
Một số nguyên \(N\).
Output
In ra một ký tự duy nhất: m hoặc o.
Constraints
- \(1 \le N \le 10^{18}\)
Sample Input 1
8
Sample Output 1
m
Sample Input 2
5
Sample Output 2
o
Explanation
Dãy bắt đầu bằng moomooomoo..., nên chữ thứ 8 là m và chữ thứ 5 là o.
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.