Binary Tree Sequence Numbering

Consider the following numbering scheme for binary trees:

• The empty tree is assigned the number $0$.
• A tree with only one node (the root) is assigned the number $1$.
• All binary trees with \(m\) nodes have numbers smaller than any binary tree with \(m+1\) nodes.
• For any binary tree with \(m\) nodes whose left subtree has number \(L\) and right subtree has number \(R\), if its assigned number is \(n\), then every \(m\mbox{-node}\) binary tree with a number greater than \(n\) either has a left subtree with a number greater than \(L\) or has the same left subtree number \(L\) and a right subtree with a number greater than \(R\).

For example, the six trees numbered from $0$ to $5$ are as follows (the letter X denotes a node):

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

Your task is: given a sequence number, output the corresponding binary tree structure.

Output Format: The tree should be printed in a serialized format defined as follows:

• An empty tree is represented by the string null.
• A non-empty tree is represented as X(L,R), where X denotes a node, and L and R are the serializations of the left and right subtrees respectively. For an empty subtree, use null in its place.

For example, a single-node tree is printed as X(null,null).

Internally, the trees are ordered first by the number of nodes (non-empty trees with fewer nodes come first) and then lexicographically by the pair ((L,R)) (comparing first the left subtree number, and if equal, the right subtree number).

Note: The number of non-empty binary trees with (m) nodes is given by the Catalan number (C_m), where (C_1=1,\ C_2=2,\ C_3=5,) etc.

Your solution must construct the tree that has the given overall sequence number according to the above numbering (with the empty tree numbered 0, and non-empty trees numbered starting from 1).

inputFormat

The input consists of a single non-negative integer (N) on a line, representing the sequence number of a binary tree. (N=0) represents the empty tree.

outputFormat

Output the serialized binary tree corresponding to the given sequence number. Use the format X(L,R) for a non-empty tree and null for an empty tree.

sample

0

null