Förutsättningarna i detta problem är desamma som i Problem F. Skillnaderna mot Problem F är understrukna.

Du får en sträng $S$ av längd $N$ som endast består av ( och ).

Besvara $Q$ frågor. I den $i$-te frågan får du heltalen $L_i$ och $R_i$. Lös följande problem:

Låt $X$ vara delsträngen av $S$ från det $L_i$-te tecknet till det $R_i$-te tecknet. Betrakta att välja ett positivt heltal $k$ och sedan välja en delsträng $Y$ av strängen som erhålls genom att konkatenera $k$ kopior av $X$. Här måste $Y$ vara en korrekt parentesföljd. $Y$ tillåts vara en tom sträng.

Avgör huruvida det existerar en största möjliga längd för $Y$, och om den existerar, bestäm detta största värde.

Korrekt parentesföljd

En korrekt parentesföljd är en sträng som kan reduceras till en tom sträng genom att upprepade gånger ta bort den sammanhängande delsträngen () noll eller flera gånger.

Indata

Indatan ges från standardinmatningen i följande format:

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

• $N, Q, L_i, R_i$ är heltal.
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $S$ är en sträng av längd $N$ som endast består av ( och ).
• $1 \le L_i \le R_i \le N$

Utdata

Skriv ut $Q$ rader. På den $i$-te raden, skriv ut den största möjliga längden på $Y$ för den $i$-te frågan om den existerar, och -1 annars.

Exempel

Exempelindata 1

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

Exempelutdata 1

-1
2
0

Förklaring

• I den första frågan är $X =$ )(. För varje positivt heltal $k$, om vi konkatenerar $k$ kopior av $X$ och tar bort det första och det sista tecknet, erhåller vi en korrekt parentesföljd av längd $2k - 2$. Därför finns det ingen största möjliga längd för $Y$, så du ska skriva ut -1.
• I den andra frågan är $X =$ ()((. Det kan bevisas att den största möjliga längden på $Y$ är $2$. Skriv därför ut 2.
• I den tredje frågan är $X =$ ((. Den största möjliga längden på $Y$ är $0$, så skriv ut 0. Observera att $Y$ kan vara en tom sträng.