Binary Tree Numbering

We define a unique numbering for all (full or empty) binary trees under the following rules:

• The empty tree is assigned the number \(0\) and the tree consisting of a single root node is assigned \(1\).
• If \(m\) is any nonnegative integer, then every binary tree with \(m\) nodes has a number less than every binary tree with \(m+1\) nodes.
• For any two different binary trees \(A\) and \(B\) with the same number of nodes, the tree with the smaller number always satisfies one of the following conditions:
  1. \(A\)'s left subtree has a smaller number than \(B\)'s left subtree, or
  2. The left subtrees are identical (i.e. have the same number) and \(A\)'s right subtree has a smaller number than \(B\)'s right subtree.
• The numbering is consecutive: every nonnegative integer uniquely corresponds to a binary tree, and every binary tree is assigned a unique nonnegative integer.

Note: In the above, when we say "binary tree" the empty tree is allowed. In our problem we represent a non‐empty node by the symbol X.

The tree is printed in the following format:

• If the tree is empty, print nothing (an empty string).
• If the tree is a leaf (both children are empty), print X.
• If the tree is non‐leaf and only the right subtree is nonempty, print X(R) where R is the representation of the right subtree.
• If only the left subtree is nonempty, print (L)X where L is the representation of the left subtree.
• If both subtrees are nonempty, print (L)X(R) where L and R are the representations of the left and right subtrees respectively.

Given a nonnegative integer \(n\) (which uniquely identifies a binary tree by the above rules), construct and print the corresponding binary tree in the format described above.

inputFormat

The input consists of a single nonnegative integer \(n\) (\(0\le n\le ...\)), representing the number assigned to a binary tree.

outputFormat

Output the representation of the binary tree corresponding to the number \(n\). The empty tree (\(n=0\)) should yield an empty output.

sample

0