시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 25 20 17 89.474%

문제

새트리는 무한 이진 트리이고, 첫 5레벨은 다음과 같이 생겼다.

새트리의 각 노드는 다음과 같이 재귀적으로 정의할 수 있다.

여기서 bird는 완전 트리를 의미하고, bird+1은 트리의 모든 분수에 1를 더하는 것을 의미하고, 1/bird는 트리의 모든 분수를 뒤집는 것을 의미한다.

놀랍게도 트리에는 모든 유리수가 딱 한 번씩 등장한다. 따라서, 모든 기약분수는 유일한 경로가 있다. 경로는 왼쪽 자식노드로 갈 때는 L, 오른쪽으로 갈 때는 R로 표현한다. 예를 들어, 2/5는 LRR로 표현할 수 있다.

기약분수가 주어졌을 때, 루트에서 그 노드까지의 경로를 L과 R로 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 a와 b가 '/'로 구분되어 주어진다. a는 기약분수의 분자, b는 분모이며, a와 b가 동시에 1인 경우는 없다. 또한, gcd(a,b) = 1을 만족한다. (1 ≤ a,b ≤ 109)

출력

첫째 줄에 루트에서 입력으로 주어진 기약분수까지 가는 경로를 출력한다. 

예제 입력 1

2/5

예제 출력 1

LRR

힌트

W3sicHJvYmxlbV9pZCI6IjM2NTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzhcdWQyYjhcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjOFx1ZDJiOFx1YjlhY1x1YjI5NCBcdWJiMzRcdWQ1NWMgXHVjNzc0XHVjOWM0IFx1ZDJiOFx1YjlhY1x1Yzc3NFx1YWNlMCwgXHVjY2FiIDVcdWI4MDhcdWJjYThcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWMwZGRcdWFjYmNcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9idC5wbmdcIiBzdHlsZT1cImhlaWdodDoyNDBweDsgd2lkdGg6NTY0cHhcIiBcLz48XC9wPlxyXG5cclxuXHJcblxyXG48cD5cdWMwYzhcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzAxIFx1YjE3OFx1YjRkY1x1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzdhY1x1YWRjMFx1YzgwMVx1YzczY1x1Yjg1YyBcdWM4MTVcdWM3NThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYmQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6ODVweDsgd2lkdGg6MjQ3cHhcIiBcLz48XC9wPlxyXG5cclxuXHJcblxyXG48cD5cdWM1ZWNcdWFlMzBcdWMxMWMgYmlyZFx1YjI5NCBcdWM2NDRcdWM4MDQgXHVkMmI4XHViOWFjXHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YWNlMCwgYmlyZCsxXHVjNzQwIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHViZDg0XHVjMjE4XHVjNWQwIDFcdWI5N2MgXHViMzU0XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NThcdWFjZTAsIDFcL2JpcmRcdWIyOTQgXHVkMmI4XHViOWFjXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWJkODRcdWMyMThcdWI5N2MgXHViNGE0XHVjOWQxXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHViMTgwXHViNzhkXHVhYzhjXHViM2M0IFx1ZDJiOFx1YjlhY1x1YzVkMFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjNzIwXHViOWFjXHVjMjE4XHVhYzAwIFx1YjUzMSBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjRmMVx1YzdhNVx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWJhYThcdWI0ZTAgXHVhZTMwXHVjNTdkXHViZDg0XHVjMjE4XHViMjk0IFx1YzcyMFx1Yzc3Y1x1ZDU1YyBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWFjYmRcdWI4NWNcdWIyOTQgXHVjNjdjXHVjYWJkIFx1Yzc5MFx1YzJkZFx1YjE3OFx1YjRkY1x1Yjg1YyBcdWFjMDggXHViNTRjXHViMjk0IEwsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWFjMDggXHViNTRjXHViMjk0IFJcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAyXC81XHViMjk0IExSUlx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48cD5cdWFlMzBcdWM1N2RcdWJkODRcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViOGU4XHVkMmI4XHVjNWQwXHVjMTFjIFx1YWRmOCBcdWIxNzhcdWI0ZGNcdWFlNGNcdWM5YzBcdWM3NTggXHVhY2JkXHViODVjXHViOTdjIExcdWFjZmMgUlx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgYVx1YzY0MCBiXHVhYzAwICYjMzk7XC8mIzM5O1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBhXHViMjk0IFx1YWUzMFx1YzU3ZFx1YmQ4NFx1YzIxOFx1Yzc1OCBcdWJkODRcdWM3OTAsIGJcdWIyOTQgXHViZDg0XHViYWE4XHVjNzc0XHViYTcwLCBhXHVjNjQwIGJcdWFjMDAgXHViM2Q5XHVjMmRjXHVjNWQwIDFcdWM3NzggXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC4gXHViNjEwXHVkNTVjLCBnY2QoYSxiKSA9IDFcdWM3NDQgXHViOWNjXHVjODcxXHVkNTVjXHViMmU0LiAoMSAmbGU7IGEsYiAmbGU7IDEwPHN1cD45PFwvc3VwPik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjhlOFx1ZDJiOFx1YzVkMFx1YzExYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWUzMFx1YzU3ZFx1YmQ4NFx1YzIxOFx1YWU0Y1x1YzljMCBcdWFjMDBcdWIyOTQgXHVhY2JkXHViODVjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNjUyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmlyZCB0cmVlIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgQmlyZCB0cmVlIGlzIGFuIGluZmluaXRlIGJpbmFyeSB0cmVlLCB3aG9zZSBcdWZiMDFyc3QgNSBsZXZlbHMgbG9vayBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2J0LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI0MHB4OyB3aWR0aDo1NjRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5JdCBjYW4gYmUgZGVmaW5lZCBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JkLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojg1cHg7IHdpZHRoOjI0N3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoaXMgaXMgYSBjby1yZWN1cnNpdmUgZGVmaW5pdGlvbiBpbiB3aGljaCBib3RoIG9jY3VycmVuY2VzIG9mIGJpcmQgcmVmZXIgdG8gdGhlIGZ1bGwgKGluZmluaXRlKSB0cmVlLjxcL3A+XHJcblxyXG48cD5UaGUgZXhwcmVzc2lvbiBiaXJkICsgMSBtZWFucyB0aGF0IDEgaXMgYWRkZWQgdG8gZXZlcnkgZnJhY3Rpb24gaW4gdGhlIHRyZWUsIGFuZCAxXC9iaXJkIG1lYW5zIHRoYXQgZXZlcnkgZnJhY3Rpb24gaW4gdGhlIHRyZWUgaXMgaW52ZXJ0ZWQgKHNvIGFcL2IgYmVjb21lcyBiXC9hKS48XC9wPlxyXG5cclxuPHA+U3VycHJpc2luZ2x5LCB0aGUgdHJlZSBjb250YWlucyBldmVyeSBwb3NpdGl2ZSByYXRpb25hbCBudW1iZXIgZXhhY3RseSBvbmNlLCBzbyBldmVyeSByZWR1Y2VkIGZyYWN0aW9uIGlzIGF0IGEgdW5pcXVlIHBsYWNlIGluIHRoZSB0cmVlLiBIZW5jZSwgd2UgY2FuIGFsc28gZGVzY3JpYmUgYSByYXRpb25hbCBudW1iZXIgYnkgZ2l2aW5nIGRpcmVjdGlvbnMgKEwgZm9yIGxlZnQgc3VidHJlZSwgUiBmb3IgcmlnaHQgc3VidHJlZSkgaW4gdGhlIEJpcmQgdHJlZS4gRm9yIGV4YW1wbGUsIDJcLzUgaXMgcmVwcmVzZW50ZWQgYnkgTFJSLiBHaXZlbiBhIHJlZHVjZWQgZnJhY3Rpb24sIHJldHVybiBhIHN0cmluZyBjb25zaXN0aW5nIG9mIEwmcnNxdW87cyBhbmQgUiZyc3F1bztzOiB0aGUgZGlyZWN0aW9ucyB0byBsb2NhdGUgdGhpcyBmcmFjdGlvbiBmcm9tIHRoZSB0b3Agb2YgdGhlIHRyZWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBhIHBvc2l0aXZlIGludGVnZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIHR3byBpbnRlZ2VycyBhIGFuZCBiICgxICZsZTsmbmJzcDthLCZuYnNwO2IgJmxlOyZuYnNwOzEwPHN1cD45PFwvc3VwPiksIHNlcGFyYXRlZCBieSBhICZyc3F1bztcLyZyc3F1bzsuIFRoZXNlIHJlcHJlc2VudCB0aGUgbnVtZXJhdG9yIGFuZCBkZW5vbWluYXRvciBvZiBhIHJlZHVjZWQgZnJhY3Rpb24uIFRoZSBpbnRlZ2VycyBhIGFuZCBiIGFyZSBub3QgYm90aCBlcXVhbCB0byAxLCBhbmQgdGhleSBzYXRpc2Z5IGdjZChhLCBiKSA9IDEuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Rm9yIGV2ZXJ5IHRlc3QgY2FzZSB0aGUgbGVuZ3RoIG9mIHRoZSBzdHJpbmcgd2l0aCBkaXJlY3Rpb25zIHdpbGwgYmUgYXQgbW9zdCAxMCAwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIHRoZSBzdHJpbmcgcmVwcmVzZW50YXRpb24gb2YgdGhlIGxvY2F0aW9uIG9mIHRoaXMgZnJhY3Rpb24gaW4gdGhlIEJpcmQgdHJlZS48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==