Nawiasy
Limit pamięci: 32 MB
Słowem nawiasowym będziemy nazywali słowo złożone
z dwóch rodzajów znaków: nawiasów otwierających, czyli "(",
oraz nawiasów zamykających, czyli ")".
Wśród wszystkich słów nawiasowych będziemy
wyróżniać poprawne wyrażenia nawiasowe.
Są to takie słowa nawiasowe, w których występujące
nawiasy można połączyć w pary w taki sposób, że:
- każda para składa się z nawiasu otwierającego
oraz (występującego dalej w słowie nawiasowym)
nawiasu zamykającego,
- dla każdej pary fragment słowa nawiasowego zawarty
między nawiasami tej pary zawiera tyle samo nawiasów
otwierających co zamykających.
Na słowie nawiasowym można wykonywać operacje:
- zamiany, która zamienia -ty nawias
w słowie na przeciwny,
- sprawdzenia, która sprawdza, czy słowo nawiasowe
jest poprawnym wyrażeniem nawiasowym.
Na pewnym słowie nawiasowym wykonywane są kolejno operacje
zamiany lub sprawdzenia.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia słowo nawiasowe
oraz ciąg operacji kolejno wykonywanych na tym słowie,
- dla każdej operacji sprawdzenia (występującej we
wczytanym ciągu operacji) stwierdzi, czy bieżące
słowo nawiasowe jest poprawnym wyrażeniem nawiasowym,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się
jedna liczba całkowita ()
oznaczająca długość słowa nawiasowego. W drugim
wierszu znajduje się n nawiasów bez znaków odstępu między nimi.
W trzecim wierszu znajduje się jedna liczba
całkowita m ()
oznaczająca liczbę operacji wykonywanych na słowie nawiasowym.
W każdym z kolejnych m wierszy znajduje się jedna
liczba całkowita.
Jeśli w ()-wierszu (dla )
występuje liczba 0, to znaczy, że k-tą z kolei
operacją wykonywaną na słowie nawiasowym jest operacja sprawdzenia.
Jeśli zaś jest to liczba całkowita p spełniająca
,
to znaczy, że operacją tą jest operacja zamiany p-tego nawiasu
na przeciwny.
Wyjście
Twój program powinien wypisać w kolejnych wierszach
(standardowego wyjścia) wyniki kolejnych operacji sprawdzenia.
Jeśli bieżące słowo nawiasowe jest poprawnym wyrażeniem
nawiasowym, to należy wypisać słowo TAK,
w przeciwnym przypadku słowo NIE.
(Na wyjściu powinno pojawić się tyle wierszy,
ile operacji sprawdzenia zadano na wejściu.)
Przykład
Dla danych wejściowych:
4
()((
4
4
0
2
0
poprawną odpowiedzią jest:
TAK
NIE
Autor zadania: Krzysztof Sikora.