피이보나치 트리

0번째와 1번째 피이보나치 트리는 각각 노드 하나로만 이루어져 있다. 1보다 큰 모든 i에 대해 i번째 피이보나치 트리는 다음 순서로 만든다.

1. 새 노드 r을 만든다. 이 노드는 i번째 피이보나치 트리의 루트가 된다.
2. (i-1)번째 피이보나치 트리와 (i-2)번째 피이보나치 트리를 만든다.
3. (i-2)번째 피이보나치 트리를 r의 왼쪽 부분 트리로 붙인다.
4. (i-1)번째 피이보나치 트리를 r의 오른쪽 부분 트리로 붙인다.

피이보나치 트리의 정점 수는 매우 빠르게 증가한다. 예를 들어 50번째 피이보나치 트리는 4 x 10^10개가 넘는 정점을 가진다.

각 정점에는 트리를 전위 순회할 때 방문하는 순서대로 번호를 매긴다.

N, 시작 위치, 도착 위치가 주어졌을 때 N번째 피이보나치 트리에서 시작 위치에서 도착 위치까지 가는 최단 경로를 구하시오. 서로 인접한 두 노드 사이의 거리는 1이다.

첫째 줄에 N, 시작 위치, 도착 위치가 공백으로 구분되어 주어진다.

N은 0 이상 50 이하인 정수이다. 시작 위치와 도착 위치는 1,000,000,000 이하의 자연수이며, 각각 N번째 피이보나치 트리의 정점 수보다 크지 않다. 두 위치는 같을 수 있다.

시작 위치에서 도착 위치까지 가는 최단 경로를 출력한다. L은 왼쪽 자식으로 이동하는 것, R은 오른쪽 자식으로 이동하는 것, U는 부모로 이동하는 것을 뜻한다. 두 위치가 같다면 아무것도 출력하지 않는다.