[HNOI2002]树的排序

题目描述

![](https://cdn.luogu.com.cn/upload/pic/1.png) 1.空树编号为0,只有根节点的树编号为1; 2.设m为一任意非负整数,那么任意一棵有m个节点的树的编号小于任意一棵有m+1个节点的树; 3.设A,B是两棵节点数相同的树(A,B不相同),则A编号比B小时,一定满足下面两个条件之一(反之亦然): (1)A左子树编号小于B左子树编号; (2)A左子树编号等于B左子树编号(即A,B左子树形态相同),且A右子树编号小于B右子树编号; 4.编号按照正常的规则,编号应是连续的非负整数,任意一棵树唯一对应一个编号,任意一个非负整数唯一对应一棵树。 (注:上述树均指二叉树)

输入输出格式

输入格式


仅1行,为一个整数n,1≦n≦500,000,000。 对于10%的数据,保证树节点个数不超过三个。

输出格式


仅1行,为对应编号为n的二叉树。按下列方式输出:  如果是一个结点的二叉树,则输出X  如果二叉树的左、右子树分别为L和R,L、R的输出形式分别为L’和R’,则输出为(L’)X(R’),当左子树为空时,输出为X(R’),当左子树为空时(L’)X。

输入输出样例

输入样例 #1

20

输出样例 #1

((X)X(X))X