Description

1. The empty tree is numbered $0$, and the tree with only the root node is numbered $1$.
2. Let $m$ be any non-negative integer. Then the number of any tree with $m$ nodes is smaller than the number of any tree with $m+1$ nodes.
3. Let $A, B$ be two trees with the same number of nodes (with $A \ne B$). The number of $A$ is smaller than that of $B$ if and only if one of the following holds:
   1. The number of the left subtree of $A$ is smaller than the number of the left subtree of $B$.
   2. The numbers of the left subtrees of $A$ and $B$ are equal (that is, the left subtrees of $A$ and $B$ have the same shape), and the number of the right subtree of $A$ is smaller than the number of the right subtree of $B$.
4. Following the usual rule, the numbers are consecutive non-negative integers. Each tree corresponds to a unique number, and each non-negative integer corresponds to a unique tree.

(Note: all trees mentioned above are binary trees.)

Input Format

A single line with an integer $n$, $1\le n\le 500{,}000{,}000$.

For $10\%$ of the testdata, the number of nodes in the tree does not exceed three.

Output Format

A single line: the binary tree corresponding to number $n$. Output as follows:

• If it is a one-node binary tree, output $X$.
• If the left and right subtrees are $L$ and $R$, and their respective outputs are $L'$ and $R'$, then output $\texttt{(}L'\texttt{)}X\texttt{(}R'\texttt{)}$; when the left subtree is empty, output $X\texttt{(}R'\texttt{)}$; when the right subtree is empty, output $\texttt{(}L'\texttt{)}X$.

20

((X)X(X))X

Hint

Translated by ChatGPT 5