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.