Este es un problema interactivo con una ejecución en dos pasos (doble ejecución).

En este problema, consideramos árboles enraizados no ordenados. Un árbol enraizado no ordenado consiste en una raíz, que puede tener cero o más hijos. Cada hijo, a su vez, es un árbol enraizado no ordenado. Como sugiere el nombre, el orden en que se enumeran los hijos no importa. Es decir, los árboles que se muestran en la siguiente figura son el mismo árbol enraizado no ordenado. En adelante, nos referiremos a los árboles enraizados no ordenados simplemente como árboles.

Cualquier árbol puede ser codificado como una secuencia de paréntesis regular (en adelante, RBS) de la siguiente manera:

• Un árbol que consiste en un único vértice se codifica como "()".
• Suponga que después de eliminar la raíz, el árbol se divide en subárboles $t_1, t_2, \ldots, t_k$, donde $k$ es el número de hijos de la raíz del árbol original. Sean $s_1, \ldots, s_k$ las cadenas que codifican los árboles $t_1, \ldots, t_k$. Entonces, para cualquier permutación $a=[a_1, a_2, ..., a_k]$ de los números del $1$ al $k$, el árbol original puede ser codificado por la RBS "($s_{a_1}s_{a_2}\ldots s_{a_k}$)".

Tenga en cuenta que el mismo árbol puede ser codificado por diferentes RBS. Por ejemplo, el árbol que se muestra en la siguiente figura puede ser codificado usando la RBS "(()(()))" o "((())())".

Necesita aprender a codificar una secuencia arbitraria de árboles $u_1, \ldots, u_n$ como un único árbol enraizado $w$. Para verificar que su método de codificación es correcto, su solución se ejecutará dos veces.

Primera ejecución

Durante la primera ejecución, su programa recibe $n$ RBS como entrada, cada una representando el código $s_i$ de algún árbol enraizado. En respuesta, su programa debe generar una RBS que codifique algún árbol enraizado $w$. En diferentes subtareas se imponen diferentes restricciones sobre el número de vértices en el árbol $w$ dependiendo del número total de vértices en los árboles originales.

Segunda ejecución

Durante la segunda ejecución, su programa recibe una única RBS que codifica el árbol $w$ que su programa generó durante la primera ejecución. Tenga en cuenta que se puede proporcionar como entrada cualquier RBS válida que codifique el árbol $w$, no necesariamente la que fue generada por su programa durante la primera ejecución.

En respuesta, su programa debe generar las RBS que codifican los mismos árboles que se proporcionaron durante la primera ejecución, en el mismo orden. Para cada árbol, puede generar cualquier RBS que lo codifique, pero el orden de los árboles en la secuencia debe ser el mismo que en la primera ejecución del programa.

Interacción

Al comienzo de cada ejecución, su programa debe leer un único entero $t$, igual a 1 o 2 — el número de ejecución.

Primera ejecución

Durante la primera ejecución, debe procesar múltiples casos de prueba. Cada caso de prueba se proporciona en la entrada estándar de forma interactiva, lo que significa que antes de leer el siguiente caso de prueba, su programa debe generar la respuesta para todos los casos de prueba anteriores y vaciar el búfer de salida estándar.

La primera línea de cada caso de prueba contiene un único entero $n$ — el número de árboles a codificar. Si $n$ es igual a $0$, significa que todos los casos de prueba han sido procesados y el programa debe terminar. En caso contrario, las siguientes $n$ líneas contienen las descripciones de los árboles.

Cada árbol se especifica mediante una única cadena $s_i$ que consiste en los caracteres "(" y ")" — la RBS que codifica el $i$-ésimo árbol de la manera descrita en el enunciado del problema. Está garantizado que $s_i$ especifica un árbol válido.

Para cada caso de prueba, el programa debe generar una RBS que codifique algún árbol $w$. Después de generar el árbol, debe generar un carácter de nueva línea y vaciar el búfer de salida.

En este problema, el comportamiento del programa del jurado durante la primera ejecución es adaptativo. Esto significa que el programa del jurado durante la primera ejecución puede usar los árboles $w$ generados por usted en casos de prueba anteriores del test actual al generar un nuevo caso de prueba.

Segunda ejecución

Durante la segunda ejecución, debe procesar múltiples casos de prueba. Cada caso de prueba se especifica mediante una cadena $s$. Si la cadena $s$ es igual a "0", entonces ha procesado todos los casos de prueba y el programa debe terminar. En caso contrario, $s$ contiene alguna RBS que codifica algún árbol $w$ que el programa construyó durante la primera ejecución.

Para cada uno de esos árboles, debe generar un único entero $n$ en una línea separada — el número de árboles decodificados.

En la siguiente línea, debe generar $n$ RBS que codifiquen, en el orden correspondiente, los mismos árboles que fueron codificados por las cadenas $s_1, \ldots, s_n$ proporcionadas durante la primera ejecución, en una sola línea, separándolos con el carácter "+". Por ejemplo, si necesita generar las RBS "(())" y "(()())" en ese orden, la salida debe ser: "2" en la primera línea, y "(()())+(()())" en la segunda línea.

Después de generar el número $n$ y la cadena que describe los árboles, debe imprimir una nueva línea y vaciar el búfer de salida.

En cada uno de los casos de prueba en la segunda ejecución, su programa puede recibir cualquiera de los árboles obtenidos durante la primera ejecución.

Nota

No olvide imprimir una nueva línea después de cada salida. Consulte la guía del concursante para aprender a vaciar correctamente el búfer de salida en problemas interactivos.

Subtareas

Sea $s$ la longitud total de las RBS en un solo caso de prueba, y $m$ el tamaño de la salida de su programa durante la primera ejecución para este caso de prueba. Para cada subtarea, se define una función $f(x)$. Una subtarea se considera superada si para cada caso de prueba se cumple $m \leq f(s)$, y también si todos los árboles fueron reconstruidos correctamente.

Sea $t_i$ el número de vértices en el $i$-ésimo árbol. Entonces la longitud de la cadena $s_i$ es $2t_i$.

Sea $S$ la suma de $s$ sobre todos los casos de prueba de un solo test. Está garantizado que en cada test $S$ no supera $10^6$, y el número de casos de prueba no supera $100$.

La cuarta subtarea se puntúa de acuerdo con la siguiente fórmula. Sea $k = \max\left(0, \dfrac{m - 2000}{s}\right)$ para cada caso de prueba. Definimos la función $\operatorname{score}(k)$ de la siguiente manera:

Para valores intermedios de $k$, la función se calcula linealmente entre filas adyacentes de la tabla y se redondea al entero más cercano.

La puntuación de un test es igual al mínimo de $\operatorname{score}(k)$ sobre todos los casos de prueba del test. La puntuación de una subtarea es igual al mínimo de las puntuaciones de los tests en esa subtarea.

Las subtareas 5, 6 y 7 también se puntúan mediante una fórmula. Sea $c = \max(0, m - s)$ para cada caso de prueba. Definimos la función $\operatorname{score}(c)$ de la siguiente manera:

Para valores intermedios de $c$, la función se calcula linealmente entre filas adyacentes de la tabla y se redondea al entero más cercano.

La puntuación de un test es igual al mínimo de $\operatorname{score}(c)$ sobre todos los casos de prueba del test. La puntuación de una subtarea es igual al mínimo de las puntuaciones de los tests en esa subtarea.

Ejemplos

Entrada 1

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

Salida 1

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

Entrada 2

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

Salida 2

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