描述

我们可以使用以下方案对二叉树进行编号：

1. 空树编号为 $0$。
2. 单节点树编号为 $1$。
3. 所有具有 $m$ 个节点的二叉树的编号小于所有具有 $m + 1$ 个节点的二叉树的编号。
4. 任何具有 $m$ 个节点且左子树为 $L$、右子树为 $R$ 的二叉树，其编号为 $n$，使得所有编号大于 $n$ 的具有 $m$ 个节点的二叉树，要么左子树的编号高于 $L$，要么左子树等于 $L$ 且右子树的编号高于 $R$。

以下展示了此序列中的前 10 棵二叉树以及编号为 20 的二叉树：

你在这个问题中的任务是，当给定二叉树的序号时，输出该二叉树。

输入

输入由多个问题实例组成。每个实例由一个整数 $n$ 组成，其中 $1 \leq n \leq 500,000,000$。当 $n = 0$ 时，输入终止。（请注意，这意味着你永远不需要输出空树。）

输出

对于每个问题实例，你应该输出一行，其中包含与该实例的序号相对应的二叉树。使用以下方案来打印二叉树：

1. 没有子节点的树应输出为 X。
2. 具有左子树 $L$ 和右子树 $R$ 的树应输出为 (L')X(R')，其中 $L'$ 和 $R'$ 是 $L$ 和 $R$ 的表示形式。
3. 如果 $L$ 为空，只需输出 X(R')。
4. 如果 $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)

来源

2001 年北美中东部地区竞赛