시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 18 14 12 92.308%

문제

새트리는 무한 이진 트리이고, 첫 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)

출력

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

예제 입력

2/5

예제 출력

LRR

힌트