Problem description

Dany jest ciąg nawiasów ( i ). Zadanie polegać będzie na weryfikacji poprawności nawiasowania dla wielu podsłów zadanego ciągu nawiasowania.

Napisz program, który wczyta ciąg nawiasów oraz zapytania o poprawność nawiasowania wybranych podsłów ciągu, wyznaczy dla każdego zapytania czy nawiasowanie jest poprawne i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i Q, oddzielone pojedynczym odstępem i określające kolejno: długość ciągu nawiasów i liczbę zapytań. W drugim wierszu znajduje się ciąg długości N złożony ze znaków ( i ).

W kolejnych Q wierszach znajduje się opis kolejnych zapytań, po jednym w wierszu. Opis każdego zapytania składa się z dwóch liczb naturalnych A_i, B_i, oddzielonych pojedynczym odstępem. Określają one zapytanie o poprawność zadanego spójnego podciągu nawiasowania od A_i-tego znaku do B_i-tego znaku.

Wyjście

Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym wierszu powinna się znaleźć odpowiedź dla i-tego zapytania. Odpowiedź dla każdego zapytania to jedno słowo TAK, jeśli nawiasowanie jest poprawne lub NIE w przeciwnym przypadku.

Ograniczenia

1 ≤ N ≤ 1 000 000, 1 ≤ Q ≤ 1 000 000.

Przykład

9 3
()(()())(
3 8
1 4
6 9

TAK
NIE
NIE