VimPlugin

Când rezolva o problemă cu un if care se întindea pe 7 rânduri, M.R. Fire și-a dat seama că de la un punct devine enervant să te asiguri că parantezele se închid corect.

Din fericire, Iron Mișu folosește și el Vim, și a decis să scrie un plugin care să îl ajute. Plugin-ul trebuie să poată procesa următoarele operații pe un șir de paranteze $S$ inițial gol:

• ’(’ adaugă o paranteză deschisă rotundă la finalul lui $S$;
• ’)’ adaugă o paranteză închisă rotundă la finalul lui $S$;
• ’[’ adaugă o paranteză deschisă dreaptă la finalul lui $S$;
• ’]’ adaugă o paranteză închisă dreaptă la finalul lui $S$;
• ’*’ șterge ultimul caracter din $S$ (dacă $S$ nu este gol);

După fiecare operație, plugin-ul afișează dacă șirul $S$ este o parantezare corectă sau nu.

Iron Mișu s-a plictisit după o vreme și a trecut la VS Code și v-a însărcinat pe voi să construiți plugin-ul de Vim.

Cerință

Dat fiind un șir de operații, afișați după fiecare dintre ele dacă șirul $S$ este corect parantezat sau nu.

Un șir parantezat corect se definește astfel:

• <șir parantezat corect> = <șirul vid>
• <șir parantezat corect> = “(” + <șir parantezat corect> + “)”
• <șir parantezat corect> = “[” + <șir parantezat corect> + “]”
• <șir parantezat corect> = <șir parantezat corect> + <șir parantezat corect>

unde + reprezintă operația de concatenare a două șiruri.

Date de intrare

Pe prima linie se va afla un număr $N$, numărul de operații.
Pe a doua linie se va afla un șir de caractere care poate conține doar caractere din mulțimea ’(‘, ‘)’, ‘[‘, ‘]’, ‘*’, reprezentând operațiile primite de plugin.

Date de ieșire

Pe prima linie se va afișa un șir de caractere format din 1 și 0. A $i$-a valoare din șir va fi 1 dacă șirul $S$ este corect parantezat după efectuarea celei de-a $i$-a operații sau 0, în caz contrar.

Restricții și precizări

• $1 \leq N \leq 10^6$

Subtask-uri

Exemple

Intrare

12
([()])[]*)*]

Ieșire

000001010001

Explicația exemplului

Cele trei 1-uri corespund șirurilor:
([()]) ; ([()])[] ; ([()])])