Balans

Se consideră un șir inițial vid pe care vrem să efectuăm $Q$ operații de următorul fel:

• se adaugă un caracter la finalul șirului;
• se elimină un caracter de la începutul șirului.
  Caracterele vor fi doar paranteze, mai exact, vor fi doar caracterele ( sau ).

Cerință

Să se determine după fiecare operație dacă secvența $S$ formată din elementele șirului formează o parantezare corectă.
O secvență se consideră parantezată corect dacă se poate transforma într-o expresie aritmetică validă adăugând doar caracterele 1 și + în secvența inițială. Spre exemplu () și (()) sunt parantezate corect pentru că putem scrie (1) respectiv ((1+1)+1), în timp ce )() sau ()) nu sunt. Șirul vid se consideră de asemenea corect parantezat.

Date de intrare

De la tastatură se va citi pe prima linie $Q$, reprezentând numărul de operații.
Pe a doua linie se vor găsi $Q$ caractere fără spații intre ele de trei tipuri:

1. ( înseamnă că se cere adăugarea caracterului ( la finalul șirului.
2. ) înseamnă că se cere adăugarea caracterului ) la finalul șirului.
3. P înseamnă că se va elimina caracterul de la începutul șirului.

Date de ieșire

Pe ecran se vor afișa $Q$ caractere, fără spații între ele, câte unul după fiecare operație, codificate în felul următor:

1. 0 înseamnă că în urma operației șirul nu este corect parantezat.
2. 1 înseamnă că în urma operației șirul este corect parantezat.

Restricții și precizări

• $1 ≤ Q ≤ 2 \cdot 10^6$
• Se garantează, că pentru fiecare $P$ citit, șirul conține cel puțin o paranteză ce se poate șterge.

Subtask 1 (13 puncte)

• Nu exista $P$ in datele de intrare.

Subtask 2 (21 puncte)

• $Q ≤ 2 \ 000$

Subtask 3 (24 puncte)

• $Q ≤ 10^5$

Subtask 4 (42 puncte)

• Fără restricții suplimentare.

Exemplu

stdin

12
(()P)PPP)(P)

stdout

000100010001

Explicații

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