这是一道通信题。

考虑在平面上从原点 $(0, 0)$ 走到 $(n, n)$，且每一步只能向右 $(\mathbf R)$ 与向上 $(\mathbf U)$ 的路径，容易发现每条路径的长度均为 $2n$，且其中恰好包含 $n$ 步向右， $n$ 步向上。众所周知，这样的路径总数共有 $\binom{2n}{n} = \frac{(2n)!}{n! \cdot n!}$ 种。

例如，$n = 2$ 时，共有以下 $6$ 种不同的路径：$\{ \mathbf{RRUU}, \mathbf{RURU}, \mathbf{RUUR}, \mathbf{URRU}, \mathbf{URUR}, \mathbf{UURR} \}$。

一个仅包含 ( 与 ) 的字符串 $U$ 被称为一个合法括号序列，当且仅当它可被通过如下方式递归定义：

• 空串是合法括号序列
• 如果 $S$ 是合法括号序列，则 $(S)$ 是合法括号序列。
• 如果 $S$ 与 $T$ 均是合法括号序列，则 $ST$ 是合法括号序列。

考虑由恰好包含 $n$ 个左括号 ( 与 $n$ 个右括号 ) 的合法括号序列，众所周知，这样的括号序列共有 $C_n = \frac{1}{n+1} \binom{2n}{n}$ 种，其中 $C_n$ 为大家最喜欢的卡特兰数。

现在你希望构造任意一个反映了这一事实的双射。具体地，给定一个长为 $2n$，且包含恰好 $n$ 个 R 与 $n$ 个 U 的字符串 $S$，你需要构造一个包含 $n$ 对括号的合法括号序列 $U$ 与一个在 $[0, n]$ 中的整数 $k$。随后，给定你所构造的合法括号序列与整数 $k$，你需要复原最初的路径。

实现细节

这是一道 ejudge 风格的通信题。在这道题中，你的程序将在每个测试点被运行两次。在第一次运行中，你需要将描述路径的字符串编码为括号序列与整数 $k$；在第二次运行中，你需要将你编码的括号序列与整数 $k$ 复原为对应的路径。

第一次运行

在第一次运行中，输入的第一行包含一个字符串 path，表示这是对你的程序的第一次运行。

接下来一行，包含一个整数 $n$，表示路径长度的一半。

接下来一行，包含一个长度为 $2n$，且只包含字符 R 与字符 U 的字符串 $S$，表示你需要编码的路径。

在第一次运行中，你需要输出恰好两行。

输出的第一行包含一个长为 $2n$ 的合法括号序列 $U$。

接下来一行，包含一个在 $[0, n]$ 中的整数 $k$。

第二次运行

在第二次运行中，输入的第一行包含一个字符串 brackets，表示这是对你的程序的第二次运行。

接下来一行，包含一个整数 $n$，表示括号序列长度的一半。

接下来一行，包含一个长度为 $2n$，且只包含字符 ( 与字符 ) 的字符串 $S$，表示你所编码的合法括号序列。

接下来一行，包含一个整数 $k$，表示你所编码的整数 $k$。

在第二次运行中，你需要输出恰好一行。

输出一行一个长度为 $2n$ 的字符串，表示你所复原的原始路径。

样例一

First Input

path
2
RRUU

First Output

(())
0

Second Input

brackets
2
(())
0

Second Output

RRUU

样例二

First Input

path
3
RUURRU

First Output

(())()
3

Second Input

brackets
3
(())()
3

Second Output

RUURRU

子任务

• Subtask 1 (10 points): $n \leq 3$
• Subtask 2 (20 points): $n \leq 6$
• Subtask 3 (70 points): 没有额外的限制

对于所有数据，保证 $1 \leq n \leq 300$。