Rammen for dette problemet er den samme som i Problem F. Forskjellene fra Problem F er understreket.

Du får gitt en streng $S$ med lengde $N$ som kun består av ( og ).

Svar på $Q$ spørringer. I den $i$-te spørringen får du gitt heltallene $L_i$ og $R_i$. Løs følgende problem:

La $X$ være delstrengen av $S$ fra det $L_i$-te tegnet til det $R_i$-te tegnet. Betrakt det å velge et positivt heltall $k$ og deretter velge en delstreng $Y$ av strengen som oppnås ved å sette sammen $k$ kopier av $X$. Her må $Y$ være en gyldig parentesfølge. $Y$ kan være en tom streng.

Avgjør om det finnes en maksimalt mulig lengde for $Y$, og hvis den finnes, finn denne maksimale verdien.

Gyldig parentesfølge

En gyldig parentesfølge er en streng som kan reduseres til en tom streng ved gjentatte ganger å fjerne den sammenhengende delstrengen () null eller flere ganger.

Inndata

Inndataene gis fra standard inndata på følgende format:

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

• $N, Q, L_i, R_i$ er heltall.
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $S$ er en streng med lengde $N$ som kun består av ( og ).
• $1 \le L_i \le R_i \le N$

Utdata

Skriv ut $Q$ linjer. På den $i$-te linjen skriver du ut den maksimalt mulige lengden av $Y$ for den $i$-te spørringen hvis den finnes, og -1 ellers.

Eksempel

Eksempelinndata 1

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

Eksempelutdata 1

-1
2
0

Merk

• I den første spørringen er $X =$ )(. For ethvert positivt heltall $k$, hvis vi setter sammen $k$ kopier av $X$ og fjerner det første og det siste tegnet, får vi en gyldig parentesfølge med lengde $2k - 2$. Derfor finnes det ingen maksimalt mulig lengde for $Y$, så du skal skrive ut -1.
• I den andre spørringen er $X =$ ()((. Det kan bevises at den maksimalt mulige lengden av $Y$ er $2$. Skriv derfor ut 2.
• I den tredje spørringen er $X =$ ((. Den maksimalt mulige lengden av $Y$ er $0$, så skriv ut 0. Merk at $Y$ kan være en tom streng.