Trees Made to Order#2176
We number all binary trees using the following scheme: - The empty tree is numbered . - The single-node tree is numbered . - All binary trees with nodes have numbers less than all trees with m+1 nodes. - Any binary tree with nodes with left and right subtrees numbered and is assigned number if and only if all -node trees with numbers greater than satisfy one of the following: - The left subtree has a number greater than , or - The left subtree has number , and the right subtree has a number greater than .
The first binary trees and the th tree in this sequence are shown below:
Your task is to reconstruct a binary tree from its order number.
The input consists of multiple test cases. Each test contains a single integer (1 \leq n \leq 500\,000\,000). The last line contains n = 0 and should not be processed. (Note that you will never have to output the empty tree.)
For each value of , output a line containing the tree corresponding to the number . Output the tree as follows:
A tree with no children should be output as X. A tree with left and right subtrees and should be output as (L')X(R'), where L' and R' are the representations of and . If is empty, output X(R'). If is empty, output (L')X.
Example 1