这是一个交互式问题，需要两次运行（双次运行）。

在此问题中，我们考虑无序有根树（unordered rooted trees）。一棵无序有根树由一个根节点组成，它可以有零个或多个子节点。每个子节点本身也是一棵无序有根树。顾名思义，子节点的排列顺序无关紧要。也就是说，下图中展示的树是同一棵无序有根树。下文中，我们将无序有根树简称为树。

任意一棵树都可以按如下方式编码为正则括号序列（以下简称 RBS）：

• 单顶点树编码为 "()"。
• 假设去掉根节点后，树拆分为子树 $t_1, t_2, \ldots, t_k$，其中 $k$ 为原树根节点的子节点个数。设 $s_1, \ldots, s_k$ 为编码子树 $t_1, \ldots, t_k$ 的字符串。则对于 $1$ 到 $k$ 的任意排列 $a=[a_1, a_2, ..., a_k]$，原树可被编码为 RBS "($s_{a_1}s_{a_2}\ldots s_{a_k}$)"。

注意，同一棵树可以被不同的 RBS 编码。例如，下图中的树既可以编码为 "(()(()))"，也可以编码为 "((())())"。

你需要学习如何将任意一个树的序列 $u_1, \ldots, u_n$ 编码为一棵单一的树 $w$。为了验证你的编码方法是否正确，你的程序将运行两次。

第一次运行

第一次运行时，你的程序读入 $n$ 个 RBS，每个 RBS 是某棵树的编码 $s_i$。作为响应，你的程序必须输出一个 RBS，该 RBS 编码了某棵树 $w$。在不同的子任务中，根据原始树的总顶点数，对 $w$ 的顶点数有不同限制。

第二次运行

第二次运行时，你的程序读入一个单一的 RBS，该 RBS 编码了你在第一次运行时输出的树 $w$。注意，输入可能是任意合法的编码了树 $w$ 的 RBS，不一定是第一次运行时你输出的那个。

作为响应，你的程序必须输出 RBS，这些 RBS 编码了第一次运行时提供的那些树，且顺序相同。对于每棵树，你可以输出任意一个它的 RBS 编码，但树在序列中的顺序必须与第一次运行时一致。

交互

每次运行开始时，你的程序必须读入一个整数 $t$，值为 1 或 2 —— 表示运行次数编号。

第一次运行

第一次运行时，你需要处理多个测试用例。每个测试用例通过标准输入以交互方式提供，这意味着在读入下一个测试用例之前，你的程序必须输出之前所有测试用例的答案，并刷新标准输出缓冲区。

每个测试用例的第一行包含一个整数 $n$ —— 需要编码的树的个数。如果 $n$ 等于 $0$，则表示所有测试用例已处理完毕，程序应终止。否则，接下来 $n$ 行包含树的描述。

每棵树由一个字符串 $s_i$ 指定，字符串由字符 "(" 和 ")" 组成 —— 这是按题目描述方式编码第 $i$ 棵树的 RBS。保证 $s_i$ 指定了一棵合法的树。

对于每个测试用例，程序必须输出一个 RBS，该 RBS 编码了某棵树 $w$。输出树后，必须输出一个换行符并刷新输出缓冲区。

在此问题中，第一次运行时的评测程序行为是自适应的。这意味着第一次运行时的评测程序在生成新测试用例时，可以利用你在当前测试中之前测试用例里输出的树 $w$。

第二次运行

第二次运行时，你需要处理多个测试用例。每个测试用例由一个字符串 $s$ 指定。如果字符串 $s$ 等于 "0"，则表示所有测试用例已处理完毕，程序应终止。否则，$s$ 包含某个 RBS，该 RBS 编码了第一次运行时程序构造的某棵树 $w$。

对于每棵这样的树，你必须在一行上输出一个整数 $n$ —— 解码得到的树的个数。

在下一行中，你必须输出 $n$ 个 RBS，按对应顺序编码第一次运行时提供的字符串 $s_1, \ldots, s_n$ 所对应的树，这些 RBS 之间用 "+" 字符分隔。例如，如果你需要按顺序输出 RBS "(())" 和 "(()())"，则第一行输出 "2"，第二行输出 "(()())+(()())"。

在输出整数 $n$ 和描述树的字符串之后，你必须打印一个换行符并刷新输出缓冲区。

第二次运行的每个测试用例中，你的程序可能会被给予第一次运行中得到的任意一棵树。

说明

每次输出后不要忘记打印换行符。请参考参赛者指南，了解如何正确刷新交互问题中的输出缓冲区。

子任务

设 $s$ 为单个测试用例中所有 RBS 的总长度，$m$ 为该测试用例中第一次运行时程序输出的大小。对于每个子任务，定义函数 $f(x)$。若对于每个测试用例都有 $m \leq f(s)$，并且所有树都被正确重构，则该子任务视为通过。

设 $t_i$ 为第 $i$ 棵树的顶点数。则字符串 $s_i$ 的长度为 $2t_i$。

设 $S$ 为单个测试中所有测试用例的 $s$ 之和。保证每个测试中 $S$ 不超过 $10^6$，且测试用例个数不超过 $100$。

第四个子任务按照以下公式计分。设每个测试用例的 $k = \max\left(0, \dfrac{m - 2000}{s}\right)$。定义函数 $\operatorname{score}(k)$ 如下：

对于 $k$ 的中间值，函数在表格相邻行之间线性计算，并四舍五入到最接近的整数。

一个测试的分数等于该测试中所有测试用例的 $\operatorname{score}(k)$ 的最小值。一个子任务的分数等于该子任务中所有测试的分数的最小值。

子任务 5、6 和 7 也使用公式计分。设每个测试用例的 $c = \max(0, m - s)$。定义函数 $\operatorname{score}(c)$ 如下：

对于 $c$ 的中间值，函数在表格相邻行之间线性计算，并四舍五入到最接近的整数。

一个测试的分数等于该测试中所有测试用例的 $\operatorname{score}(c)$ 的最小值。一个子任务的分数等于该子任务中所有测试的分数的最小值。

样例

输入 1

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

输出 1

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

输入 2

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

输出 2

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