트리의 순서

다음 과정에 따라 모든 이진 트리에 번호를 매길 수 있다.

• 비어 있는 트리의 번호는 $0$이다.

• 노드가 $1$개인 트리의 번호는 $1$이다.

• 노드가 $m$개인 트리의 번호는 노드가 $m+1$개인 트리의 번호보다 항상 작다. 즉, 노드 수가 적은 트리일수록 번호가 작다.

• 노드 수가 같은 두 트리의 순서는 다음과 같이 정한다. 왼쪽 서브트리가 $L$, 오른쪽 서브트리가 $R$인 트리는, 노드 수가 같으면서 아래 두 조건 중 하나라도 만족하는 트리보다 번호가 작다.

  • 왼쪽 서브트리의 번호가 $L$의 번호보다 큰 트리, 또는
  • 왼쪽 서브트리가 $L$과 같고, 오른쪽 서브트리의 번호가 $R$의 번호보다 큰 트리.

  다시 말해, 노드 수가 같은 트리들은 (왼쪽 서브트리 번호, 오른쪽 서브트리 번호) 쌍을 사전순으로 비교하여 정렬한 순서와 같다.

처음 $10$개($0$번부터 $9$번까지)의 이진 트리와 $20$번째 이진 트리를 그림으로 나타내면 아래와 같다.

        0  1  2      3  4      5      6      7      8  9        ...     20

           X  X      X  X      X      X      X      X  X                 X
               \    /    \      \    / \    /      /    \               /
                X  X      X      X  X   X  X      X      X             X
                           \    /           \    /        \           / \
                            X  X             X  X          X         X   X
                                                            \
                                                             X

정수 $n$이 주어졌을 때, $n$번째 이진 트리를 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 줄에 정수 $n$이 하나씩 주어진다. ($1 \le n \le 500{,}000{,}000$)

$n = 0$이 입력되면 입력이 끝난 것이므로 프로그램을 종료한다.

각 테스트 케이스마다 해당 트리를 아래 규칙에 따라 한 줄에 출력한다.

왼쪽 서브트리 $L$과 오른쪽 서브트리 $R$을 출력한 문자열을 각각 $L'$, $R'$이라 하자.

• 자식이 없는 트리(잎 노드 하나)는 X로 출력한다.
• $L$과 $R$이 모두 비어 있지 않으면 (L')X(R') 형태로 출력한다.
• $L$이 비어 있으면 X(R')로 출력한다.
• $R$이 비어 있으면 (L')X로 출력한다.