#P1814. 数的序号

数的序号

题目描述

我们可以用下面的方案给二叉树标号:

  • 空树的序号为 00
  • 只有一个根结点的树序号为 11
  • 所有包含 mm 个结点的二叉树的序号一定比任何一个包含 m+1m+1 个结点的二叉树的序号小。
  • 对于任何一棵二叉树,设其左子树序号为 LL,右子树序号为 RR,且它有 mm 个结点,若它的序号为 nn,则所有序号大于 nnmm 个结点的二叉树,要么左子树序号大于 LL,要么左子树序号等于 LL 且右子树序号大于 RR

例如,编号为 0055 的六棵树形状如下:

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

你的任务就是对给定的序号,输出该序号所对应的二叉树。

输入格式

本题有多组数据。

输入的每行有一个非负整数 nnn=0n=0 表示输入结束,此时不需要输出 n=0n=0 的空树。

输出格式

对于每组数据,输出一行,代表序号 nn 对应的树。

一棵二叉树的表示为 (L)X(R),其中 L,RL,R 分别是左子树和右子树的表示,如一侧为空则省略,例如只有左子树则表示为 (L)X

1   
20 
31117532   
0 
X
((X)X(X))X
(X(X(((X(X))X(X))X(X))))X(((X((X)X((X)X)))X)X)

提示

数据规模与约定

对于所有测试点,保证 1n5×1081\le n\le 5\times10^8,数据组数不超过 5050