Tämän tehtävän asetelma on sama kuin tehtävässä F. Erot tehtävään F on alleviivattu.

Annettuna on pituutta $N$ oleva merkkijono $S$, joka koostuu vain merkeistä ( ja ).

Vastaa $Q$ kyselyyn. $i$-nnessä kyselyssä annetaan kokonaisluvut $L_i$ ja $R_i$. Ratkaise seuraava tehtävä:

Olkoon $X$ merkkijonon $S$ osamerkkijono $L_i$-nnestä merkistä $R_i$-nteen merkkiin. Tarkastellaan positiivisen kokonaisluvun $k$ valitsemista ja sen jälkeen sellaisen osamerkkijonon $Y$ valitsemista, joka saadaan ketjuttamalla $k$ kopiota merkkijonosta $X$. Tässä $Y$:n täytyy olla säännöllinen sulkulauseke. $Y$ saa olla tyhjä merkkijono.

Määritä, onko $Y$:lle olemassa suurinta mahdollista pituutta, ja jos on, etsi tämä suurin arvo.

Säännöllinen sulkulauseke

Säännöllinen sulkulauseke on merkkijono, joka voidaan supistaa tyhjäksi merkkijonoksi poistamalla toistuvasti yhtenäinen osamerkkijono () nolla tai useampia kertoja.

Syöte

Syöte annetaan vakiosyötteestä seuraavassa muodossa:

N Q
S
L_1 R_1
L_2 R_2
...
L_Q R_Q

• $N, Q, L_i, R_i$ ovat kokonaislukuja.
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $S$ on pituutta $N$ oleva merkkijono, joka koostuu vain merkeistä ( ja ).
• $1 \le L_i \le R_i \le N$

Tuloste

Tulosta $Q$ riviä. Tulosta $i$-nnelle riville $Y$:n suurin mahdollinen pituus $i$-nnessä kyselyssä, jos sellainen on olemassa, ja muuten -1.

Esimerkki

Esimerkkisyöte 1

4 3
()((
2 3
1 4
3 4

Esimerkkituloste 1

-1
2
0

Huomautus

• Ensimmäisessä kyselyssä $X =$ )(. Mille tahansa positiiviselle kokonaisluvulle $k$, jos ketjutamme $k$ kopiota merkkijonosta $X$ ja poistamme ensimmäisen ja viimeisen merkin, saamme säännöllisen sulkulausekkeen, jonka pituus on $2k - 2$. Näin ollen $Y$:lle ei ole suurinta mahdollista pituutta, joten sinun tulee tulostaa -1.
• Toisessa kyselyssä $X =$ ()((. Voidaan todistaa, että $Y$:n suurin mahdollinen pituus on $2$. Tulosta siis 2.
• Kolmannessa kyselyssä $X =$ ((. $Y$:n suurin mahdollinen pituus on $0$, joten tulosta 0. Huomaa, että $Y$ voi olla tyhjä merkkijono.