Ce problème est interactif et s’exécute en deux passes (double exécution).

Dans ce problème, nous considérons des arbres enracinés non ordonnés. Un arbre enraciné non ordonné consiste en une racine qui peut avoir zéro ou plusieurs enfants. Chaque enfant est à son tour un arbre enraciné non ordonné. Comme le nom l’indique, l’ordre dans lequel les enfants sont listés n’a pas d’importance. Autrement dit, les arbres représentés dans la figure ci-dessous sont le même arbre enraciné non ordonné. Dans la suite, nous désignerons les arbres enracinés non ordonnés simplement par arbres.

Tout arbre peut être encodé par une suite de parenthèses régulières (ci-après RBS) de la manière suivante :

• Un arbre constitué d’un seul sommet est encodé par "()".
• Supposons qu’après avoir retiré la racine, l’arbre se divise en sous-arbres $t_1, t_2, \dots, t_k$, où $k$ est le nombre d’enfants de la racine de l’arbre original. Soient $s_1,\dots, s_k$ les chaînes qui encodent les arbres $t_1,\dots, t_k$. Alors, pour toute permutation $a=[a_1,a_2,\dots,a_k]$ des nombres $1$ à $k$, l’arbre original peut être encodé par la RBS "($s_{a_1}s_{a_2}\dots s_{a_k}$)".

Notez qu’un même arbre peut être encodé par différentes RBS. Par exemple, l’arbre représenté dans la figure ci-dessous peut être encodé par la RBS "(()(()))" ou par "((())())".

Vous devez apprendre à encoder une séquence quelconque d’arbres $u_1, \dots, u_n$ en un seul arbre enraciné $w$. Pour vérifier que votre méthode d’encodage est correcte, votre solution sera exécutée deux fois.

Première exécution

Lors de la première exécution, votre programme reçoit en entrée $n$ RBS, chacune représentant le code $s_i$ d’un certain arbre enraciné. En réponse, votre programme doit afficher une RBS qui encode un certain arbre enraciné $w$. Selon les sous-tâches, différentes contraintes sont imposées sur le nombre de sommets de l’arbre $w$ en fonction du nombre total de sommets des arbres originaux.

Deuxième exécution

Lors de la deuxième exécution, votre programme reçoit une unique RBS qui encode l’arbre $w$ que votre programme a affiché lors de la première exécution. Notez que n’importe quelle RBS valide encodant l’arbre $w$ peut être fournie en entrée, pas nécessairement celle qui a été affichée par votre programme lors de la première exécution.

En réponse, votre programme doit afficher les RBS qui encodent les mêmes arbres que ceux fournis lors de la première exécution, dans le même ordre. Pour chaque arbre, vous pouvez afficher n’importe quelle RBS l’encodant, mais l’ordre des arbres eux‑mêmes dans la séquence doit être le même que lors de la première exécution du programme.

Interaction

Au début de chaque exécution, votre programme doit lire un unique entier $t$, égal à 1 ou 2 — le numéro de l’exécution.

Première exécution

Lors de la première exécution, vous devez traiter plusieurs cas de test. Chaque cas de test est fourni sur l’entrée standard de manière interactive, ce qui signifie qu’avant de lire le cas de test suivant, votre programme doit afficher la réponse pour tous les cas de test précédents et vider le tampon de sortie standard.

La première ligne de chaque cas de test contient un unique entier $n$ — le nombre d’arbres à encoder. Si $n$ vaut $0$, cela signifie que tous les cas de test ont été traités et que le programme doit se terminer. Sinon, les $n$ lignes suivantes contiennent les descriptions des arbres.

Chaque arbre est spécifié par une unique chaîne $s_i$ constituée des caractères "(" et ")" — la RBS qui encode le $i$-ème arbre de la manière décrite dans l’énoncé du problème. Il est garanti que $s_i$ spécifie un arbre valide.

Pour chaque cas de test, le programme doit afficher une RBS qui encode un certain arbre $w$. Après avoir affiché l’arbre, vous devez afficher un retour à la ligne et vider le tampon de sortie.

Dans ce problème, le comportement du programme du jury lors de la première exécution est adaptatif. Cela signifie que le programme du jury peut utiliser les arbres $w$ que vous avez affichés dans les cas de test précédents du test en cours pour générer un nouveau cas de test.

Deuxième exécution

Lors de la deuxième exécution, vous devez traiter plusieurs cas de test. Chaque cas de test est spécifié par une chaîne $s$. Si la chaîne $s$ est égale à "0", alors vous avez traité tous les cas de test et le programme doit se terminer. Sinon, $s$ contient une RBS encodant un certain arbre $w$ que le programme a construit lors de la première exécution.

Pour chacun de ces arbres, vous devez afficher un unique entier $n$ sur une ligne séparée — le nombre d’arbres décodés.

Sur la ligne suivante, vous devez afficher $n$ RBS qui encodent, dans l’ordre correspondant, les mêmes arbres que ceux encodés par les chaînes $s_1,\dots,s_n$ fournies lors de la première exécution, sur une seule ligne, en les séparant par le caractère "+". Par exemple, si vous devez afficher les RBS "(())" et "(()())" dans cet ordre, la sortie doit être : "2" sur la première ligne, et "(()())+(()())" sur la deuxième ligne.

Après avoir affiché le nombre $n$ et affiché la chaîne décrivant les arbres, vous devez afficher un retour à la ligne et vider le tampon de sortie.

Dans chacun des cas de test de la deuxième exécution, votre programme peut recevoir n’importe lequel des arbres obtenus lors de la première exécution.

Remarque

N’oubliez pas d’afficher un retour à la ligne après chaque sortie. Référez‑vous au guide du participant pour apprendre à vider correctement le tampon de sortie dans les problèmes interactifs.

Sous‑tâches

Soit $s$ la longueur totale des RBS dans un seul cas de test, et $m$ la taille de la sortie de votre programme lors de la première exécution pour ce cas de test. Pour chaque sous‑tâche, une fonction $f(x)$ est définie. Une sous‑tâche est considérée comme réussie si pour chaque cas de test $m \le f(s)$ et si tous les arbres ont été correctement reconstruits.

Soit $t_i$ le nombre de sommets dans le $i$-ème arbre. Alors la longueur de la chaîne $s_i$ est $2t_i$.

Soit $S$ la somme des $s$ sur tous les cas de test d’un seul test. Il est garanti que dans chaque test $S$ ne dépasse pas $10^6$ et que le nombre de cas de test ne dépasse pas $100$.

La quatrième sous‑tâche est notée selon la formule suivante. Soit $k = \max\left(0, \dfrac{m - 2000}{s}\right)$ pour chaque cas de test. On définit la fonction $\operatorname{score}(k)$ comme suit :

Pour les valeurs intermédiaires de $k$, la fonction est calculée linéairement entre les lignes adjacentes du tableau et arrondie à l’entier le plus proche.

Le score pour un test est égal au minimum de $\operatorname{score}(k)$ sur tous les cas de test du test. Le score pour une sous‑tâche est égal au minimum des scores des tests de cette sous‑tâche.

Les sous‑tâches 5, 6 et 7 sont également notées à l’aide d’une formule. Soit $c = \max(0, m - s)$ pour chaque cas de test. On définit la fonction $\operatorname{score}(c)$ comme suit :

Pour les valeurs intermédiaires de $c$, la fonction est calculée linéairement entre les lignes adjacentes du tableau et arrondie à l’entier le plus proche.

Le score pour un test est égal au minimum de $\operatorname{score}(c)$ sur tous les cas de test du test. Le score pour une sous‑tâche est égal au minimum des scores des tests de cette sous‑tâche.

Exemples

Entrée 1

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

Sortie 1

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

Entrée 2

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

Sortie 2

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