시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 43 25 22 84.615%

문제

새트리는 무한 이진 트리이고, 첫 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) 경로의 길이는 10,000을 넘지 않는다.

출력

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

예제 입력 1

2/5

예제 출력 1

LRR
W3sicHJvYmxlbV9pZCI6IjM2NTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzhcdWQyYjhcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjOFx1ZDJiOFx1YjlhY1x1YjI5NCBcdWJiMzRcdWQ1NWMgXHVjNzc0XHVjOWM0IFx1ZDJiOFx1YjlhY1x1Yzc3NFx1YWNlMCwgXHVjY2FiIDVcdWI4MDhcdWJjYThcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWMwZGRcdWFjYmNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYnQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjQwcHg7IHdpZHRoOjU2NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzBjOFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMDEgXHViMTc4XHViNGRjXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjN2FjXHVhZGMwXHVjODAxXHVjNzNjXHViODVjIFx1YzgxNVx1Yzc1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JkLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojg1cHg7IHdpZHRoOjI0N3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzVlY1x1YWUzMFx1YzExYyBiaXJkXHViMjk0IFx1YzY0NFx1YzgwNCBcdWQyYjhcdWI5YWNcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHVhY2UwLCBiaXJkKzFcdWM3NDAgXHVkMmI4XHViOWFjXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWJkODRcdWMyMThcdWM1ZDAgMVx1Yjk3YyBcdWIzNTRcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YWNlMCwgMVwvYmlyZFx1YjI5NCBcdWQyYjhcdWI5YWNcdWM3NTggXHViYWE4XHViNGUwIFx1YmQ4NFx1YzIxOFx1Yjk3YyBcdWI0YTRcdWM5ZDFcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMTgwXHViNzhkXHVhYzhjXHViM2M0IFx1ZDJiOFx1YjlhY1x1YzVkMFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjNzIwXHViOWFjXHVjMjE4XHVhYzAwIFx1YjUzMSBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjRmMVx1YzdhNVx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWJhYThcdWI0ZTAgXHVhZTMwXHVjNTdkXHViZDg0XHVjMjE4XHViMjk0IFx1YzcyMFx1Yzc3Y1x1ZDU1YyBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWFjYmRcdWI4NWNcdWIyOTQgXHVjNjdjXHVjYWJkIFx1Yzc5MFx1YzJkZFx1YjE3OFx1YjRkY1x1Yjg1YyBcdWFjMDggXHViNTRjXHViMjk0IEwsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWFjMDggXHViNTRjXHViMjk0IFJcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAyXC81XHViMjk0IExSUlx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZTMwXHVjNTdkXHViZDg0XHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjhlOFx1ZDJiOFx1YzVkMFx1YzExYyBcdWFkZjggXHViMTc4XHViNGRjXHVhZTRjXHVjOWMwXHVjNzU4IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBMXHVhY2ZjIFJcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIGFcdWM2NDAgYlx1YWMwMCAmIzM5O1wvJiMzOTtcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gYVx1YjI5NCBcdWFlMzBcdWM1N2RcdWJkODRcdWMyMThcdWM3NTggXHViZDg0XHVjNzkwLCBiXHViMjk0IFx1YmQ4NFx1YmFhOFx1Yzc3NFx1YmE3MCwgYVx1YzY0MCBiXHVhYzAwIFx1YjNkOVx1YzJkY1x1YzVkMCAxXHVjNzc4IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuIFx1YjYxMFx1ZDU1YywgZ2NkKGEsYikgPSAxXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNC4gKDEgJmxlOyBhLGIgJmxlOyAxMDxzdXA+OTxcL3N1cD4pJm5ic3A7XHVhY2JkXHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAxMCwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjhlOFx1ZDJiOFx1YzVkMFx1YzExYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWUzMFx1YzU3ZFx1YmQ4NFx1YzIxOFx1YWU0Y1x1YzljMCBcdWFjMDBcdWIyOTQgXHVhY2JkXHViODVjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM2NTIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCaXJkIHRyZWUiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBCaXJkIHRyZWUgaXMgYW4gaW5maW5pdGUgYmluYXJ5IHRyZWUsIHdob3NlIFx1ZmIwMXJzdCA1IGxldmVscyBsb29rIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYnQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjQwcHg7IHdpZHRoOjU2NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkl0IGNhbiBiZSBkZWZpbmVkIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYmQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6ODVweDsgd2lkdGg6MjQ3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhpcyBpcyBhIGNvLXJlY3Vyc2l2ZSBkZWZpbml0aW9uIGluIHdoaWNoIGJvdGggb2NjdXJyZW5jZXMgb2YgYmlyZCByZWZlciB0byB0aGUgZnVsbCAoaW5maW5pdGUpIHRyZWUuPFwvcD5cclxuXHJcbjxwPlRoZSBleHByZXNzaW9uIGJpcmQgKyAxIG1lYW5zIHRoYXQgMSBpcyBhZGRlZCB0byBldmVyeSBmcmFjdGlvbiBpbiB0aGUgdHJlZSwgYW5kIDFcL2JpcmQgbWVhbnMgdGhhdCBldmVyeSBmcmFjdGlvbiBpbiB0aGUgdHJlZSBpcyBpbnZlcnRlZCAoc28gYVwvYiBiZWNvbWVzIGJcL2EpLjxcL3A+XHJcblxyXG48cD5TdXJwcmlzaW5nbHksIHRoZSB0cmVlIGNvbnRhaW5zIGV2ZXJ5IHBvc2l0aXZlIHJhdGlvbmFsIG51bWJlciBleGFjdGx5IG9uY2UsIHNvIGV2ZXJ5IHJlZHVjZWQgZnJhY3Rpb24gaXMgYXQgYSB1bmlxdWUgcGxhY2UgaW4gdGhlIHRyZWUuIEhlbmNlLCB3ZSBjYW4gYWxzbyBkZXNjcmliZSBhIHJhdGlvbmFsIG51bWJlciBieSBnaXZpbmcgZGlyZWN0aW9ucyAoTCBmb3IgbGVmdCBzdWJ0cmVlLCBSIGZvciByaWdodCBzdWJ0cmVlKSBpbiB0aGUgQmlyZCB0cmVlLiBGb3IgZXhhbXBsZSwgMlwvNSBpcyByZXByZXNlbnRlZCBieSBMUlIuIEdpdmVuIGEgcmVkdWNlZCBmcmFjdGlvbiwgcmV0dXJuIGEgc3RyaW5nIGNvbnNpc3Rpbmcgb2YgTCZyc3F1bztzIGFuZCBSJnJzcXVvO3M6IHRoZSBkaXJlY3Rpb25zIHRvIGxvY2F0ZSB0aGlzIGZyYWN0aW9uIGZyb20gdGhlIHRvcCBvZiB0aGUgdHJlZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIGEgcG9zaXRpdmUgaW50ZWdlcjogdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggdHdvIGludGVnZXJzIGEgYW5kIGIgKDEgJmxlOyZuYnNwO2EsJm5ic3A7YiAmbGU7Jm5ic3A7MTA8c3VwPjk8XC9zdXA+KSwgc2VwYXJhdGVkIGJ5IGEgJnJzcXVvO1wvJnJzcXVvOy4gVGhlc2UgcmVwcmVzZW50IHRoZSBudW1lcmF0b3IgYW5kIGRlbm9taW5hdG9yIG9mIGEgcmVkdWNlZCBmcmFjdGlvbi4gVGhlIGludGVnZXJzIGEgYW5kIGIgYXJlIG5vdCBib3RoIGVxdWFsIHRvIDEsIGFuZCB0aGV5IHNhdGlzZnkgZ2NkKGEsIGIpID0gMS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Gb3IgZXZlcnkgdGVzdCBjYXNlIHRoZSBsZW5ndGggb2YgdGhlIHN0cmluZyB3aXRoIGRpcmVjdGlvbnMgd2lsbCBiZSBhdCBtb3N0IDEwIDAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggdGhlIHN0cmluZyByZXByZXNlbnRhdGlvbiBvZiB0aGUgbG9jYXRpb24gb2YgdGhpcyBmcmFjdGlvbiBpbiB0aGUgQmlyZCB0cmVlLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=