Suluavaldised

문제

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

• $()()$ on suluavaldis;
• kui $ss$ on suluavaldis, siis ka $(s)(s)$ on suluavaldis;
• kui $ss$ ja $tt$ on suluavaldised, siis ka $stst$ on suluavaldis.

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

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

Antud $LL$ ja $RR$. Kas leidub selline $kk$, et ning $A_L{A}_{L+1}\dots A_{k}A\_L\; A\_\{L\; +\; 1\}\; \backslash ldots\; A\_k$ ja $A_{k+1}{A}_{k+2}\dots A_{R}A\_\{k\; +\; 1\}\; A\_\{k\; +\; 2\}\; \backslash ldots\; A\_R$ on mõlemad suluavaldised? Väljasta JAH, kui leidub, ning EI, kui ei leidu.

Sõne $AA$ positsioonid on nummerdatud $1,\dots ,N1,\; \backslash ldots,\; N$.

입력

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

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

Järgmisel $MM$ real on igaühel kaks tühikuga eraldatud täisarvu $LL$ ja $RR$ (), mis kirjeldavad päringuid.

출력

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

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

JAH
EI
EI