Đàn bò đã trở nên say mê một trò chơi chữ mới có tên “Moo”. Trò chơi được chơi bởi một nhóm bò đứng thành một hàng dài, trong đó lần lượt mỗi con bò chịu trách nhiệm đọc thật nhanh một chữ cái cụ thể. Con bò đầu tiên mắc lỗi sẽ thua.

Dãy chữ cái trong Moo về nguyên tắc có thể kéo dài mãi mãi. Dãy bắt đầu như sau:

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

Cách mô tả tốt nhất cho dãy là dùng đệ quy: gọi \(S(0)\) là dãy 3 ký tự m o o. Sau đó, dãy dài hơn \(S(k)\) được tạo bằng cách lấy một bản sao của \(S(k-1)\), tiếp theo là m o ... o với \(k+2\) chữ o, rồi thêm một bản sao khác của \(S(k-1)\). Ví dụ:

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"

Như bạn có thể thấy, quá trình này cuối cùng tạo nên một chuỗi dài vô hạn, và đây chính là chuỗi ký tự được dùng trong trò chơi Moo.

Bessie cảm thấy mình rất thông minh và muốn dự đoán ký tự thứ \(N\) của chuỗi này là m hay o. Hãy giúp cô!

Dữ liệu vào

Dòng 1 chứa một số nguyên duy nhất \(N\) (\(1 \le N \le 10^9\)).

Dữ liệu ra

Dòng duy nhất của dữ liệu ra chứa một ký tự duy nhất, là m hoặc o.

Ví dụ

11

m

Nguồn

USACO 2012 February Contest, Bronze - Moo: https://usaco.org/index.php?page=viewproblem2&cpid=114

Tác giả: Brian Dean, 2012.