Tämän tehtävän asetelma on sama kuin tehtävässä G. Erot tehtävään G 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.

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 Finite, jos $i$-nnessä kyselyssä $Y$:lle on olemassa suurin mahdollinen pituus, ja muuten Infinite.

Esimerkki

Esimerkkisyöte 1

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

Esimerkkituloste 1

Infinite
Finite
Finite

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 Infinite.
• Toisessa kyselyssä $X =$ ()((. Voidaan todistaa, että $Y$:n suurin mahdollinen pituus on $2$. Tulosta siis Finite.
• Kolmannessa kyselyssä $X =$ ((. $Y$:n suurin mahdollinen pituus on $0$, joten tulosta Finite. Huomaa, että $Y$ voi olla tyhjä merkkijono.