Nawiasy kwadratowe kontratakują

To zadanie pochodzi z Kółka Informatycznego w Staszicu.

Mamy dany ciąg n nawiasów kwadratowych; każdy nawias może być otwierający lub zamykający. Ciąg taki jest poprawnym ciągiem nawiasów, jeśli można każdemu otwierającemu nawiasowi przyporządkować jego zamykający, tj. ciąg [][[]][] jest poprawny, ale []][ już nie.

Na danym początkowym ciągu nawiasów Jaś chce móc dokonywać następujące operacje: obrócić p-ty nawias w drugą stronę oraz swierdzić, czy w tym momencie ciąg nawiasów jest poprawnym ciągiem nawiasów. Napisz program, który mu pomoże.

Wejście

W pierwszej linii wejścia jest liczba parzysta 2 <= n <= 100 000, oznaczająca liczbę nawiasów. Druga linia wejścia zawiera n liczb 1 lub -1 oddzielonych spacjami, 1 oznacza otwarcie nawiasu, -1 - zamknięcie. Kolejne linie zawierają polecenia Jasia: linia z liczbą p > 0 oznacza, że p-ty nawias należy przekręcić w drugą stronę (nawiasy są numerowane od 1); linia z liczbą 0 oznacza, że należy odpowiedzieć na pytanie czy aktualny ciąg nawiasów jest poprawny. Linia z -1 kończy dane wejściowe.

Wyjście

Na każde polecenie 0 (czyli zapytanie, czy ciąg jest poprawny) należy wypisać jedną linię zawierającą TAK lub NIE, w zależności od tego, czy ciąg jest poprawny.

Przykład

Dla danych wejściowych

8
1 1 -1 1 1 -1 -1 -1
0
2
0
7
0
3
0
5
0
-1

prawidłową odpowiedzią jest:

TAK
NIE
NIE
NIE
TAK