Order of Trees

Time limit1sMemory limit128 MB

Summary

Given n, print the n-th binary tree under a canonical ordering by node count and by (left subtree number, right subtree number) recursively.

Level: Hard8 of 10
Topics: Combinatorics, Dynamic programming, Recursion, Math
Solved: No attempts yet

Problem

You can assign a number to every binary tree using the following process.

The empty tree has number $0$ .
The tree with a single node has number $1$ .
A binary tree with $m$ nodes always has a smaller number than any binary tree with $m+1$ nodes. In other words, a tree with fewer nodes gets a smaller number.
To order two trees that have the same number of nodes, consider a tree with left subtree $L$ and right subtree $R$ . This tree has a smaller number than any tree with the same number of nodes that satisfies at least one of the following:
- its left subtree has a larger number than $L$ , or
- its left subtree equals $L$ and its right subtree has a larger number than $R$ .
Equivalently, trees with the same number of nodes are sorted by the pair (number of the left subtree, number of the right subtree) in lexicographic order.

The first $10$ binary trees (numbers $0$ through $9$ ) and the $20$ th binary tree are shown below.

        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

Given an integer $n$ , write a program that finds the $n$ -th binary tree.

Input

The input consists of several test cases. Each line contains one integer $n$ ( $1 \le n \le 500{,}000{,}000$ ).

When $n = 0$ is given, the input ends and the program should terminate.

Output

For each test case, print the corresponding tree on its own line using the following rules.

Let $L'$ and $R'$ be the printed results of the left subtree $L$ and the right subtree $R$ , respectively.

A tree with no children (a single leaf node) is printed as X.
If neither $L$ nor $R$ is empty, print (L')X(R').
If $L$ is empty, print X(R').
If $R$ is empty, print (L')X.

Examples3

Example 1

Input

Expected output

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

Example 2
Input
```
1
0
```
Expected output
```
X
```
Example 3
Input
```
2
3
0
```
Expected output
```
X(X)
(X)X
```