Umgerð þessa verkefnis er sú sama og í Verkefni F. Munurinn frá Verkefni F er undirstrikaður.

Gefinn er strengur $S$ af lengd $N$ sem samanstendur eingöngu af ( og ).

Svaraðu $Q$ fyrirspurnum. Í $i$-tu fyrirspurninni eru gefnar heiltölurnar $L_i$ og $R_i$. Leystu eftirfarandi verkefni:

Látum $X$ vera hlutstreng $S$ frá $L_i$-ta staf til $R_i$-ta stafs. Hugsum okkur að velja jákvæða heiltölu $k$ og velja síðan hlutstreng $Y$ úr strengnum sem fæst með því að skeyta saman $k$ eintökum af $X$. Hér verður $Y$ að vera regluleg svigaruna. $Y$ má vera tómur strengur.

Ákvarðaðu hvort til sé mesta mögulega lengd fyrir $Y$, og ef hún er til, finndu það hámarksgildi.

Regluleg svigaruna

Regluleg svigaruna er strengur sem hægt er að minnka niður í tóman streng með því að fjarlægja ítrekað samfellda hlutstrenginn () núll eða fleiri sinnum.

Inntak

Inntakið er gefið úr staðalinntaki á eftirfarandi sniði:

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

• $N, Q, L_i, R_i$ eru heiltölur.
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $S$ er strengur af lengd $N$ sem samanstendur eingöngu af ( og ).
• $1 \le L_i \le R_i \le N$

Úttak

Prentaðu $Q$ línur. Fyrir $i$-tu línuna skaltu prenta mestu mögulegu lengd $Y$ fyrir $i$-tu fyrirspurnina ef hún er til, en -1 annars.

Dæmi

Dæmi um inntak 1

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

Dæmi um úttak 1

-1
2
0

Athugasemd

• Í fyrstu fyrirspurninni er $X =$ )(. Fyrir sérhverja jákvæða heiltölu $k$, ef við skeytum saman $k$ eintökum af $X$ og fjarlægjum fyrsta og síðasta stafinn, fáum við reglulega svigarunu af lengd $2k - 2$. Því er engin mesta mögulega lengd til fyrir $Y$, svo þú ættir að prenta -1.
• Í annarri fyrirspurninni er $X =$ ()((. Hægt er að sanna að mesta mögulega lengd $Y$ er $2$. Prentaðu því 2.
• Í þriðju fyrirspurninni er $X =$ ((. Mesta mögulega lengd $Y$ er $0$, svo prentaðu 0. Athugaðu að $Y$ getur verið tómur strengur.