题目描述

对二叉树 $T$ 来说，$L(T)$ 表示 $T$ 的根的左子树，$R(T)$ 表示 $T$ 的根的右子树。

二叉树 $T$ 与二叉树 $S$ 的大小关系定义如下：

• 首先，结点数少的二叉树更小；
• 其次，若结点数相同，则比较 $L(S)$ 与$L(T)$，左子树更小的二叉树更小；
• 若左子树也一样大，则比较 $R(S)$ 与$R(T)$，右子树更小的二叉树更小。

将所有二叉树按照上述规则排序，对于一个给定的整数 $n$，输出第 $n$ 个位置上的二叉树的中序序列。

二叉树 $T$ 的中序序列定义如下：

• 先输出 $L(T)$ 的中序序列，并在外加一层括号，若 $L(T)$ 为空则跳过这步
• 再输出一个 *
• 最后输出 $R(T)$ 的中序序列，并在外加一层括号，若 $R(T)$ 为空则跳过这步

输入格式

• 单个整数表示 $n$。

输出格式

• 单个字符串表示二叉树的中序遍历结果。

1

*

2

*(*)

数据范围

• $30\%$ 的数据，$1\leq n\leq 10^3$
• $60\%$ 的数据，$1\leq n\leq 10^{9}$
• $100\%$ 的数据，$1\leq n\leq 10^{16}$