시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB85052773207434.781%

문제

Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다.

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 

Moo 수열은 다음과 같은 방법으로 재귀적으로 만들 수 있다. 먼저, S(0)을 길이가 3인 수열 "m o o"이라고 하자. 1보다 크거나 같은 모든 k에 대해서, S(k)는 S(k-1)과 o가 k+2개인 수열 "m o ... 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이 주어졌을 때, Moo 수열의 N번째 글자를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 109)이 주어진다.

출력

N번째 글자를 출력한다.

예제 입력 1

11

예제 출력 1

m
W3sicHJvYmxlbV9pZCI6IjU5MDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJNb28gXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5Nb29cdWIyOTQgXHVjMjIwXHVjNzkwXHViOWFjXHVjNWQwXHVjMTFjIFx1Yzk5MFx1YWM4MVx1YWM4YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDAgTW9vXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NzQgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM2NzhcdWNlNThcdWJhNzQgXHViNDE4XHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+TW9vIFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWFlMzhcdWM3NzRcdWFjMDAgXHViYjM0XHVkNTVjXHViMzAwXHVjNzc0XHViYTcwLCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzBkZFx1YWNiY1x1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHByZT5cclxubSBvIG8gbSBvIG8gbyBtIG8gbyBtIG8gbyBvIG8gbSBvIG8gbSBvIG8gbyBtIG8gbyBtIG8gbyBvIG8gbyZuYnNwOzxcL3ByZT5cclxuXHJcbjxwPk1vbyBcdWMyMThcdWM1ZjRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVjN2FjXHVhZGMwXHVjODAxXHVjNzNjXHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJhM2NcdWM4MDAsIFMoMClcdWM3NDQgXHVhZTM4XHVjNzc0XHVhYzAwIDNcdWM3NzggXHVjMjE4XHVjNWY0ICZxdW90O20gbyBvJnF1b3Q7XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YmFhOFx1YjRlMCBrXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgUyhrKVx1YjI5NCBTKGstMSlcdWFjZmMgb1x1YWMwMCBrKzJcdWFjMWNcdWM3NzggXHVjMjE4XHVjNWY0ICZxdW90O20gbyAuLi4gbyZxdW90OyBcdWM2NDAgUyhrLTEpXHVjNzQ0IFx1ZDU2OVx1Y2NkMFx1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuUygwKSA9ICZxdW90O20gbyBvJnF1b3Q7XHJcblMoMSkgPSAmcXVvdDttIG8gbyBtIG8gbyBvIG0gbyBvJnF1b3Q7XHJcblMoMikgPSAmcXVvdDttIG8gbyBtIG8gbyBvIG0gbyBvIG0gbyBvIG8gbyBtIG8gbyBtIG8gbyBvIG0gbyBvJnF1b3Q7PFwvcHJlPlxyXG5cclxuPHA+XHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWMyZGRcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0XHViYTc0LCBcdWFlMzhcdWM3NzRcdWFjMDAgXHViYjM0XHVkNTVjXHViMzAwXHVjNzc4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhZGY4IFx1YzIxOFx1YzVmNFx1Yzc0NCBNb28gXHVjMjE4XHVjNWY0XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+Tlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBNb28gXHVjMjE4XHVjNWY0XHVjNzU4IE5cdWJjODhcdWM5ZjggXHVhZTAwXHVjNzkwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOICgxICZsZTsgTiAmbGU7IDEwPHN1cD45PFwvc3VwPilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk5cdWJjODhcdWM5ZjggXHVhZTAwXHVjNzkwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI1OTA0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTW9vIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgY293cyBoYXZlIGdvdHRlbiB0aGVtc2VsdmVzIGhvb2tlZCBvbiBhIG5ldyB3b3JkIGdhbWUsIGNhbGxlZCAmcXVvdDtNb28mcXVvdDsuICZuYnNwO0l0IGlzIHBsYXllZCBieSBhIGdyb3VwIG9mIGNvd3Mgc3RhbmRpbmcgaW4gYSBsb25nIGxpbmUsIHdoZXJlIGVhY2ggY293IGluIHNlcXVlbmNlIGlzIHJlc3BvbnNpYmxlIGZvciBjYWxsaW5nIG91dCBhIHNwZWNpZmljIGxldHRlciBhcyBxdWlja2x5IGFzIHBvc3NpYmxlLiAmbmJzcDtUaGUgZmlyc3QgY293IHdobyBtYWtlcyBhIG1pc3Rha2UgbG9zZXMuPFwvcD5cclxuXHJcbjxwPlRoZSBzZXF1ZW5jZSBvZiBsZXR0ZXJzIGluIE1vbyBjYW4gdGVjaG5pY2FsbHkgY29udGludWUgZm9yZXZlci4gJm5ic3A7SXQgc3RhcnRzIGxpa2UgdGhpczo8XC9wPlxyXG5cclxuPHByZT5cclxubSBvIG8gbSBvIG8gbyBtIG8gbyBtIG8gbyBvIG8gbSBvIG8gbSBvIG8gbyBtIG8gbyBtIG8gbyBvIG8gbyZuYnNwOzxcL3ByZT5cclxuXHJcbjxwPlRoZSBzZXF1ZW5jZSBpcyBiZXN0IGRlc2NyaWJlZCByZWN1cnNpdmVseTogbGV0IFMoMCkgYmUgdGhlIDMtY2hhcmFjdGVyIHNlcXVlbmNlICZxdW90O20gbyBvJnF1b3Q7LiAmbmJzcDtUaGVuIGEgbG9uZ2VyIHNlcXVlbmNlIFMoaykgaXMgb2J0YWluZWQgYnkgdGFraW5nIGEgY29weSBvZiB0aGUgc2VxdWVuY2UgUyhrLTEpLCB0aGVuICZxdW90O20gbyAuLi4gbyZxdW90OyB3aXRoIGsrMiBvJiMzOTtzLCBhbmQgdGhlbiBhbm90aGVyIGNvcHkgb2YgdGhlIHNlcXVlbmNlIFMoay0xKS4gJm5ic3A7Rm9yIGV4YW1wbGU6PFwvcD5cclxuXHJcbjxwcmU+XHJcblMoMCkgPSAmcXVvdDttIG8gbyZxdW90O1xyXG5TKDEpID0gJnF1b3Q7bSBvIG8gbSBvIG8gbyBtIG8gbyZxdW90O1xyXG5TKDIpID0gJnF1b3Q7bSBvIG8gbSBvIG8gbyBtIG8gbyBtIG8gbyBvIG8gbSBvIG8gbSBvIG8gbyBtIG8gbyZxdW90OzxcL3ByZT5cclxuXHJcbjxwPkFzIHlvdSBjYW4gc2VlLCB0aGlzIHByb2Nlc3MgdWx0aW1hdGVseSBidWlsZHMgYW4gaW5maW5pdGVseSBsb25nIHN0cmluZywgYW5kIHRoaXMgaXMgdGhlIHN0cmluZyBvZiBjaGFyYWN0ZXJzIHVzZWQgZm9yIHRoZSBnYW1lIG9mIE1vby48XC9wPlxyXG5cclxuPHA+QmVzc2llIHRoZSBjb3csIGZlZWxpbmcgY2xldmVyLCB3aXNoZXMgdG8gcHJlZGljdCB3aGV0aGVyIHRoZSBOdGggY2hhcmFjdGVyIG9mIHRoaXMgc3RyaW5nIHdpbGwgYmUgYW4gJnF1b3Q7bSZxdW90OyBvciBhbiAmcXVvdDtvJnF1b3Q7LiAmbmJzcDtQbGVhc2UgaGVscCBoZXIgb3V0ITxcL3A+XHJcbiIsImlucHV0IjoiPHA+KiBMaW5lIDE6IEEgc2luZ2xlIGludGVnZXIgTiAoMSAmbHQ7PSBOICZsdDs9IDEwXjkpLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4qIExpbmUgMTogVGhlIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gYSBzaW5nbGUgY2hhcmFjdGVyLCB3aGljaCBpcyBlaXRoZXIgbSBvciBvLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > USA Computing Olympiad > 2011-2012 Season > USACO February 2012 Contest > Bronze 3번