This is an interactive problem with a two-pass execution (double run).

In this problem, we consider unordered rooted trees. An unordered rooted tree consists of a root, which can have zero or more children. Each child, in turn, is an unordered rooted tree. As the name suggests, the order in which the children are listed does not matter. That is, the trees shown in the figure below are the same unordered rooted tree. Hereinafter, we will refer to unordered rooted trees simply as trees.

Any tree can be encoded as a regular bracket sequence (hereinafter, RBS) as follows:

• A tree consisting of a single vertex is encoded as "()".
• Suppose that after removing the root, the tree splits into subtrees $t_1, t_2, \ldots, t_k$, where $k$ is the number of children of the root of the original tree. Let $s_1, \ldots, s_k$ be the strings that encode the trees $t_1, \ldots, t_k$. Then for any permutation $a=[a_1, a_2, ..., a_k]$ of numbers from $1$ to $k$, the original tree can be encoded by the RBS "($s_{a_1}s_{a_2}\ldots s_{a_k}$)".

Note that the same tree can be encoded by different RBSs. For example, the tree shown in the figure below can be encoded using the RBS "(()(()))" or "((())())".

You need to learn how to encode an arbitrary sequence of trees $u_1, \ldots, u_n$ as a single rooted tree $w$. To verify that your encoding method is correct, your solution will be run twice.

First run

During the first run, your program receives $n$ RBSs as input, each representing the code $s_i$ of some rooted tree. In response, your program must output an RBS that encodes some rooted tree $w$. In different subtasks, different constraints are imposed on the number of vertices in the tree $w$ depending on the total number of vertices in the original trees.

Second run

During the second run, your program receives a single RBS that encodes the tree $w$ that your program outputted during the first run. Note that any valid RBS encoding the tree $w$ can be provided as input, not necessarily the one that was outputted by your program during the first run.

In response, your program must output the RBSs that encode the same trees that were provided during the first run, in the same order. For each tree, you can output any RBS encoding it, but the order of the trees themselves in the sequence must be the same as in the first run of the program.

Interaction

At the beginning of each run, your program must read a single integer $t$, equal to 1 or 2 — the run number.

First run

During the first run, you need to process multiple test cases. Each test case is provided on the standard input interactively, meaning that before reading the next test case, your program must output the answer for all previous test cases and flush the standard output buffer.

The first line of each test case contains a single integer $n$ — the number of trees to encode. If $n$ is equal to $0$, it means that all test cases have been processed and the program should terminate. Otherwise, the next $n$ lines contain the descriptions of the trees.

Each tree is specified by a single string $s_i$ consisting of characters "(" and ")" — the RBS that encodes the $i$-th tree in the manner described in the problem statement. It is guaranteed that $s_i$ specifies a valid tree.

For each test case, the program must output an RBS that encodes some tree $w$. After outputting the tree, you must output a newline character and flush the output buffer.

In this problem, the behavior of the jury's program during the first run is adaptive. This means that the jury's program during the first run can use the trees $w$ outputted by you in previous test cases of the current test when generating a new test case.

Second run

During the second run, you need to process multiple test cases. Each test case is specified by a string $s$. If the string $s$ is equal to "0", then you have processed all test cases, and the program should terminate. Otherwise, $s$ contains some RBS encoding some tree $w$ that the program constructed during the first run.

For each such tree, you must output a single integer $n$ on a separate line — the number of decoded trees.

In the next line, you must output $n$ RBSs that encode, in the corresponding order, the same trees that were encoded by the strings $s_1, \ldots, s_n$ provided during the first run, in a single line, separating them with the "+" character. For example, if you need to output the RBSs "(())" and "(()())" in that order, the output should be: "2" in the first line, and "(()())+(()())" in the second line.

After outputting the number $n$ and outputting the string describing the trees, you must print a newline and flush the output buffer.

In each of the test cases in the second run, your program can be given any of the trees obtained during the first run.

Note

Do not forget to print a newline after each output. Refer to the contestant's guide to learn how to properly flush the output buffer in interactive problems.

Subtasks

Let $s$ be the total length of the RBSs in a single test case, and $m$ be the size of your program's output during the first run for this test case. For each subtask, a function $f(x)$ is defined. A subtask is considered passed if for each test case $m \leq f(s)$ holds, and also if all trees were correctly reconstructed.

Let $t_i$ be the number of vertices in the $i$-th tree. Then the length of the string $s_i$ is $2t_i$.

Let $S$ be the sum of $s$ over all test cases of a single test. It is guaranteed that in each test $S$ does not exceed $10^6$, and the number of test cases does not exceed $100$.

The fourth subtask is scored according to the following formula. Let $k = \max\left(0, \dfrac{m - 2000}{s}\right)$ for each test case. We define the function $\operatorname{score}(k)$ as follows:

For intermediate values of $k$, the function is calculated linearly between adjacent rows of the table and rounded to the nearest integer.

The score for a test is equal to the minimum of $\operatorname{score}(k)$ over all test cases in the test. The score for a subtask is equal to the minimum of the scores of the tests in this subtask.

Subtasks 5, 6, and 7 are also scored using a formula. Let $c = \max(0, m - s)$ for each test case. We define the function $\operatorname{score}(c)$ as follows:

For intermediate values of $c$, the function is calculated linearly between adjacent rows of the table and rounded to the nearest integer.

The score for a test is equal to the minimum of $\operatorname{score}(c)$ over all test cases in the test. The score for a subtask is equal to the minimum of the scores of the tests in this subtask.

Examples

Input 1

1
3
()
(())
(()())
1
((())())
0

Output 1

((()(()())))
((((((((()))))))))

Input 2

2
((((((((()))))))))
(((()())()))
0

Output 2

1
(()(()))
3
()+(())+(()())