Description

We can label binary trees using the following scheme:

• The empty tree has index $0$.
• The tree with only a root node has index $1$.
• All binary trees with $m$ nodes have indices smaller than any binary tree with $m+1$ nodes.
• For any binary tree, let its left-subtree index be $L$, its right-subtree index be $R$, and it have $m$ nodes. If its index is $n$, then for all $m$-node binary trees whose indices are greater than $n$, either their left-subtree index is greater than $L$, or their left-subtree index equals $L$ and their right-subtree index is greater than $R$.

For example, the six trees with indices $0$ through $5$ have the following shapes:

0   1   2       3   4       5 
    X   X       X   X       X
         \     /     \       \
          X   X       X       X
                       \     /
                        X   X

Your task is to output the binary tree corresponding to a given index.

Input Format

This problem has multiple test cases.

Each line contains a non-negative integer $n$. $n=0$ indicates the end of input, and you do not need to output the empty tree for $n=0$.

Output Format

For each test case, output one line representing the tree corresponding to index $n$.

A binary tree is represented as (L)X(R), where $L$ and $R$ are the representations of the left and right subtrees, respectively. If one side is empty, omit it; for example, if there is only a left subtree, it is represented as (L)X.

1   
20 
31117532   
0 

X
((X)X(X))X
(X(X(((X(X))X(X))X(X))))X(((X((X)X((X)X)))X)X)

Hint

Constraints

对于所有测试点，保证 $1\le n\le 5\times10^8$，数据组数不超过 $50$。

Translated by ChatGPT 5