This is a communication problem.

Consider a path from the origin $(0, 0)$ to $(n, n)$ in the plane, where each step can only be to the right $(\mathbf R)$ or upward $(\mathbf U)$. It is easy to see that every such path has a length of $2n$ and contains exactly $n$ steps to the right and $n$ steps upward. It is well known that the total number of such paths is $\binom{2n}{n} = \frac{(2n)!}{n! \cdot n!}$.

For example, when $n = 2$, there are $6$ different paths: $\{ \mathbf{RRUU}, \mathbf{RURU}, \mathbf{RUUR}, \mathbf{URRU}, \mathbf{URUR}, \mathbf{UURR} \}$.

A string $U$ consisting only of ( and ) is called a valid parenthesis sequence if and only if it can be defined recursively as follows:

• The empty string is a valid parenthesis sequence.
• If $S$ is a valid parenthesis sequence, then $(S)$ is a valid parenthesis sequence.
• If $S$ and $T$ are both valid parenthesis sequences, then $ST$ is a valid parenthesis sequence.

Consider valid parenthesis sequences containing exactly $n$ left parentheses ( and $n$ right parentheses ). It is well known that there are $C_n = \frac{1}{n+1} \binom{2n}{n}$ such sequences, where $C_n$ is the Catalan number.

You are asked to construct a bijection that reflects this fact. Specifically, given a string $S$ of length $2n$ containing exactly $n$ Rs and $n$ Us, you need to construct a valid parenthesis sequence $U$ containing $n$ pairs of parentheses and an integer $k$ in the range $[0, n]$. Subsequently, given the constructed valid parenthesis sequence and the integer $k$, you need to recover the original path.

Implementation Details

This is an ejudge-style communication problem. In this problem, your program will be executed twice for each test case. In the first execution, you need to encode the string representing the path into a parenthesis sequence and an integer $k$; in the second execution, you need to recover the original path from the encoded parenthesis sequence and the integer $k$.

First Execution

In the first execution, the first line of input contains the string path, indicating that this is the first execution of your program.

The next line contains an integer $n$, representing half the length of the path.

The next line contains a string $S$ of length $2n$, consisting only of characters R and U, representing the path you need to encode.

In the first execution, you must output exactly two lines.

The first line of output contains a valid parenthesis sequence $U$ of length $2n$.

The next line contains an integer $k$ in the range $[0, n]$.

Second Execution

In the second execution, the first line of input contains the string brackets, indicating that this is the second execution of your program.

The next line contains an integer $n$, representing half the length of the parenthesis sequence.

The next line contains a string $S$ of length $2n$, consisting only of characters ( and ), representing the valid parenthesis sequence you encoded.

The next line contains an integer $k$, representing the integer $k$ you encoded.

In the second execution, you must output exactly one line.

Output a single string of length $2n$, representing the recovered original path.

Examples

Input 1

path
2
RRUU

Output 1

(())
0

Input 2

brackets
2
(())
0

Output 2

RRUU

Input 3

path
3
RUURRU

Output 3

(())()
3

Input 4

brackets
3
(())()
3

Output 4

RUURRU

Subtasks

• Subtask 1 (10 points): $n \leq 3$
• Subtask 2 (20 points): $n \leq 6$
• Subtask 3 (70 points): No additional constraints

For all test cases, it is guaranteed that $1 \leq n \leq 300$.