시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB19131168.750%

문제

Suluavaldiseks nimetatakse sõnet, mis on saadud järgmiste reeglite abil:

  • $()$ on suluavaldis;
  • kui $s$ on suluavaldis, siis ka $(s)$ on suluavaldis;
  • kui $s$ ja $t$ on suluavaldised, siis ka $st$ on suluavaldis.

Näiteks ()(), (())() ja (()()) on suluavaldised, aga (()(, )( ja kala ei ole.

Meil on antud sõne $A$ pikkusega $N$, mis koosneb ainult sümbolitest ( ja ). Lisaks on antud $M$ päringut, millest igaüks on kujul:

Antud $L$ ja $R$. Kas leidub selline $k$, et $L < k < R$ ning $A_L A_{L + 1} \ldots A_k$ ja $A_{k + 1} A_{k + 2} \ldots A_R$ on mõlemad suluavaldised? Väljasta JAH, kui leidub, ning EI, kui ei leidu.

Sõne $A$ positsioonid on nummerdatud $1, \ldots, N$.

입력

Sisendi esimesel real on täisarvud $N$ ja $M$ ($2 \le N \le 10^6$, $1 \le M \le 10^6$) --- sisendsõne pikkus ja päringute arv.

Teisel real on sõne $A$: täpselt $N$ sümbolit, millest igaüks on ( või ).

Järgmisel $M$ real on igaühel kaks tühikuga eraldatud täisarvu $L$ ja $R$ ($1 \le L < R \le N$), mis kirjeldavad päringuid.

출력

Väljundisse kirjutada päringute vastused, igaüks eraldi reale.

예제 입력 1

9 3
(()(()))(
2 7
1 8
7 9

예제 출력 1

JAH
EI
EI

Esimesele päringule vastab alamsõne ()(()). Selle saab tükeldada suluavaldisteks () ja (()): sobiv $k$ on 3.

Teisele päringule vastab alamsõne (()(())). Kuigi see sõne on ise suluavaldis, ei ole seda võimalik kaheks suluavaldiseks tükeldada.

Kolmandale päringule vastab alamsõne ))(, mis pole ise suluavaldis ja mida ei saa ka sulu\-avaldisteks tükeldada.