분수 탐색

스턴-브로콧 트리(Stern-Brocot tree)는 0/1과 1/0 사이의 모든 양의 분수를 포함하는 이진 트리이다.

트리의 루트는 1/1이다. 임의의 노드 a/b에서 왼쪽 자식은 a/b와 이전 왼쪽 경계의 중앙값, 오른쪽 자식은 a/b와 이전 오른쪽 경계의 중앙값이다.

서로소인 양의 정수 a, b가 주어질 때, 루트(1/1)에서 a/b까지의 경로를 구하시오. 왼쪽으로 이동하면 L, 오른쪽으로 이동하면 R로 표기한다.