これは2回実行（ダブルラン）を伴うインタラクティブ問題です。

本問題では順序なし根付き木を考えます。順序なし根付き木は、根と、その根が持つ0個以上の子からなります。各子はまた順序なし根付き木です。名前の通り、子の順序は重要ではありません。つまり、以下の図に示す木はすべて同じ順序なし根付き木です。以下では、順序なし根付き木を単に木と呼びます。

任意の木は、以下の方法で正しい括弧列（以下 RBS）に符号化できます。

• 1頂点のみからなる木は "()" と符号化されます。
• 根を取り除いた後、木が部分木 $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 で符号化されることがあることに注意してください。例えば、下図の木は RBS "(()(()))" または "((())())" で符号化できます。

あなたは、任意の木の列 $u_1, \ldots, u_n$ を1つの根付き木 $w$ に符号化する方法を学ぶ必要があります。符号化方法が正しいことを検証するため、あなたの解答は2回実行されます。

1回目の実行

1回目の実行では、プログラムは入力として $n$ 個の RBS を受け取ります。それぞれはある根付き木の符号 $s_i$ を表します。これに対してプログラムは、ある根付き木 $w$ を符号化した RBS を出力しなければなりません。小課題に応じて、木 $w$ の頂点数に対して、元の木の頂点数の合計に依存する異なる制約が課されます。

2回目の実行

2回目の実行では、プログラムは、1回目の実行でプログラムが出力した木 $w$ を符号化する1つの RBS を受け取ります。入力として与えられるのは、木 $w$ を符号化する任意の正しい RBS であり、必ずしも1回目の実行でプログラムが出力したものとは限らないことに注意してください。

これに対してプログラムは、1回目の実行で与えられたものと同じ木たちを符号化する RBS を、同じ順序で出力しなければなりません。各木については、それを符号化する任意の RBS を出力して構いませんが、列内の木の順序は1回目のプログラム実行時と同じでなければなりません。

インタラクション

各実行の開始時に、プログラムは1つの整数 $t$（1または2） — 実行番号 — を読み込まなければなりません。

1回目の実行

1回目の実行では、複数のテストケースを処理する必要があります。各テストケースは標準入力にインタラクティブに与えられます。すなわち、次のテストケースを読み込む前に、プログラムはそれまでのすべてのテストケースに対する答えを出力し、標準出力バッファをフラッシュしなければなりません。

各テストケースの1行目には、1つの整数 $n$ — 符号化する木の数 — が含まれます。$n$ が $0$ の場合は、すべてのテストケースが処理されたことを意味し、プログラムは終了しなければなりません。それ以外の場合、次の $n$ 行には木の記述が含まれます。

各木は、文字 "(" と ")" からなる1つの文字列 $s_i$ で指定されます。これは、問題文で説明された方法で $i$ 番目の木を符号化した RBS です。$s_i$ が正しい木を指定することは保証されています。

各テストケースについて、プログラムは何らかの木 $w$ を符号化する RBS を出力しなければなりません。木を出力した後、改行を出力し、出力バッファをフラッシュしなければなりません。

この問題では、1回目の実行におけるジャッジプログラムの動作は適応的です。すなわち、1回目の実行のジャッジプログラムは、現在のテスト中にそれ以前のテストケースであなたが出力した木 $w$ を、新しいテストケースを生成する際に利用することができます。

2回目の実行

2回目の実行では、複数のテストケースを処理する必要があります。 各テストケースは文字列 $s$ で指定されます。文字列 $s$ が "0" の場合は、すべてのテストケースが処理されたことを意味し、プログラムは終了しなければなりません。 それ以外の場合、$s$ は、1回目の実行でプログラムが構築した何らかの木 $w$ を符号化する RBS を含みます。

そのような木のそれぞれに対して、プログラムは別の行に1つの整数 $n$ — 復号された木の数 — を出力しなければなりません。

次の行では、1回目の実行で与えられた文字列 $s_1, \ldots, s_n$ によって符号化されたものと同じ木たちを対応する順序で符号化する $n$ 個の RBS を、1行に "+" 文字で区切って出力しなければなりません。例えば、RBS "(())" と "(()())" をこの順序で出力する必要がある場合、出力は1行目に "2"、2行目に "(()())+(()())" となります。

数 $n$ を出力し、木を記述する文字列を出力した後、改行を出力し、出力バッファをフラッシュしなければなりません。

2回目の実行の各テストケースでは、プログラムは1回目の実行で得られた任意の木を与えられます。

注記

出力のたびに改行を出力するのを忘れないでください。インタラクティブ問題における出力バッファの適切なフラッシュ方法については、参加者ガイドを参照してください。

小課題

1つのテストケース内の RBS の長さの合計を $s$、このテストケースに対する1回目の実行でのプログラムの出力のサイズを $m$ とします。 各小課題に対して関数 $f(x)$ が定義されます。各テストケースについて $m \leq f(s)$ が成り立ち、かつすべての木が正しく復元された場合、その小課題は合格とみなされます。

$i$ 番目の木の頂点数を $t_i$ とします。このとき、文字列 $s_i$ の長さは $2t_i$ です。

1つのテストにおける全テストケースにわたる $s$ の合計を $S$ とします。各テストにおいて $S$ は $10^6$ を超えず、テストケースの数は $100$ を超えないことが保証されています。

第4小課題は以下の式に従って採点されます。各テストケースについて $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
()+(())+(()())