arh

Dexter și-a definit propriul algoritm de arhivare a șirului favorit $T$, șir format numai din litere mici ale alfabetului englez. Șirul arhivat, notat cu $S$, poate fi format din cifre, litere mici ale alfabetului englez, parantezele drepte [ și ] și parantezele rotunde ( și ), precum și caractere *.

Fixi, curios din fire, descoperă algoritmul și încearcă să dezarhiveze șirul $S$, prin efectuarea unor transformări repetate. O transformare poate fi de unul dintre cele $3$ tipuri de mai jos, unde s-a notat cu $C$ o secvență din $S$ formată numai din litere.

1. O secvență a lui $S$ de forma n(C), unde n este numărul natural poziționat imediat înaintea parantezei rotunde, se transformă într-o secvență $D$ obținută prin scrierea concatenată, de $n$ ori, a șirului $C$.
   Exemplu: pentru secvența 10(ab) avem $n=10$ și se obține secvența $D=$ abababababababababab.
2. O secvență a lui $S$ de forma [*C] se transformă într-o secvență palindromică de lungime pară, obținută prin concatenarea secvenței $C$ cu oglinditul lui $C$.
   Exemplu: din secvența [*abc] se obține secvența palindromică de lungime pară abccba
3. O secvență a lui $S$ de forma [C*] se transformă într-o secvență palindromică de lungime impară, obținută prin concatenarea secvenței $C$ cu oglinditul lui $C$ din care s-a eliminat primul caracter.
   Exemplu: din secvența [abc*] se obține secvența palindromică de lungime impară abcba.

Un șir se consideră dezarhivat dacă este format numai din litere mici ale alfabetului englez.

Cerințe

Fiind dat șirul arhivat $S$ să se determine numărul de transformări, de cele $3$ tipuri de mai sus, realizate de Fixi în cadrul algoritmului de dezarhivare, precum și forma finală dezarhivată $T$ a șirului $S$.

Date de intrare

Fișierul de intrare arh.in conține șirul de caractere arhivat S.

Date de ieșire

Fișierul de ieșire arh.out conține obligatoriu două linii. Pe prima linie numărul de transformări cerut, iar pe linia a doua șirul de caractere cerut, $T$.

Restricții și precizări

• Lungimea șirului arhivat $S$ este cuprinsă între $1$ și $10 \ 000$, inclusiv;
• Lungimea șirului dezarhivat $T$ este cuprinsă între $1$ și $100 \ 000$, inclusiv;
• $2 \leq n \leq 1 \ 000$;
• O secvență a unui șir este o succesiune de caractere aflate pe poziții consecutive în şir;
• În șirul $S$:
  • O cifră poate apărea numai imediat înaintea unei paranteze rotunde deschise sau imediat înaintea unei alte cifre;
  • Fiecare paranteză rotundă deschisă are imediat înaintea sa cel puțin o cifră;
  • Toate parantezele, drepte sau rotunde, se închid corect;
  • Caracterul * poate apărea numai imediat după o paranteză dreaptă deschisă sau imediat înaintea unei paranteze drepte închise.
• O secvenţă a unui șir este palindromică dacă primul element al secvenţei este egal cu ultimul, al doilea cu penultimul etc;
• Oglinditul unei secvențe se obține prin scriere în ordine inversă a caracterelor sale;
• Se acordă $20\%$ din punctajul fiecărui test pentru scrierea corectă a numărului cerut și $80\%$ din punctajul fiecărui test pentru scrierea corectă a șirului cerut;
• Pentru $30$ de puncte șirul arhivat $S$ poate fi dezarhivat numai cu transformări de tipul $1$;
• Pentru alte $30$ de puncte șirul arhivat $S$ poate fi dezarhivat numai cu transformări de tipurile $2$ și $3$.

Exemplul 1

arh.in

2(a)[*a2(b)]xy[2(c)b*]d

arh.out

5
aaabbbbaxyccbccd

Explicație

2(a) => aa
2(b) => bb
[*a2(b)] => [*abb] => abbbba
2(c) => cc
[2(c)b*] => [ccb*] => ccbcc

Exemplul 2

arh.in

2(ab[cd*])a3(xyz)

arh.out

3
abcdcabcdcaxyzxyzxyz

Explicație

3(xyz) => xyzxyzxyz
[cd*] => cdc
2(ab[cd*]) => 2(abcdc) => abcdcabcdc

Exemplul 3

arh.in

abcd

arh.out

0
abcd

Explicație

Nu este nevoie de nicio transformare, iar șirul dezarhivat este identic cu cel arhivat.