29868번 - Suluavaldised 다국어

문제

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.

제한

힌트