새트리

새트리(Bird tree)는 무한 이진 트리입니다. 각 노드에는 양의 유리수가 하나씩 들어 있고, 루트 노드에는 $1/1$이 들어 있습니다.

트리 전체를 bird라고 할 때, 다음 두 연산을 정의합니다.

• $\text{bird}+1$: 트리에 들어 있는 모든 분수에 $1$을 더해서 얻는 트리
• $1/\text{bird}$: 트리에 들어 있는 모든 분수를 역수로 뒤집어서 얻는 트리

새트리는 재귀적으로 정의됩니다. 루트에는 $1/1$이 있고, 루트의 왼쪽 서브트리는 $1/(\text{bird}+1)$이며 오른쪽 서브트리는 $1/\text{bird}+1$입니다. 즉, 왼쪽 서브트리는 새트리 전체의 모든 분수 $x$를 $\frac{1}{x+1}$로 바꾼 트리이고, 오른쪽 서브트리는 모든 분수 $x$를 $\frac{1}{x}+1=\frac{x+1}{x}$로 바꾼 트리입니다.

놀랍게도 이 트리에는 모든 양의 유리수가 정확히 한 번씩 나타납니다. 따라서 모든 기약분수는 루트에서 그 노드까지 가는 경로가 유일합니다. 경로는 왼쪽 자식으로 내려갈 때 $L$, 오른쪽 자식으로 내려갈 때 $R$로 나타냅니다. 예를 들어 $2/5$는 경로 $LRR$로 표현됩니다.

기약분수가 주어졌을 때, 루트에서 그 분수가 있는 노드까지 가는 경로를 $L$과 $R$로 출력하는 프로그램을 작성하세요.

첫째 줄에 기약분수가 $a/b$ 꼴로 주어집니다. 여기서 $a$는 분자, $b$는 분모이며 문자 /로 구분됩니다. $a$와 $b$가 동시에 $1$인 경우는 없고, $\gcd(a, b) = 1$을 만족합니다. ($1 \le a, b \le 10^9$) 경로의 길이는 $10{,}000$을 넘지 않습니다.

첫째 줄에 루트에서 입력으로 주어진 기약분수가 있는 노드까지 가는 경로를 $L$과 $R$로 이루어진 문자열로 출력합니다.