Бұл есептің шарты F есебімен бірдей. F есебінен айырмашылықтарының асты сызылған.

Сізге тек ( және ) таңбаларынан тұратын ұзындығы $N$ болатын $S$ жолы берілген.

$Q$ сұранысқа жауап беріңіз. $i$-ші сұраныста сізге $L_i$ және $R_i$ бүтін сандары беріледі. Келесі есепті шығарыңыз:

$X$ арқылы $S$ жолының $L_i$-ші таңбасынан $R_i$-ші таңбасына дейінгі ішкі жолын белгілейік. Оң бүтін $k$ санын таңдап, содан кейін $X$ жолының $k$ көшірмесін біріктіру арқылы алынған жолдың $Y$ ішкі жолын таңдауды қарастырайық. Мұнда $Y$ дұрыс жақшалар тізбегі болуы керек. $Y$ бос жол болуы мүмкін.

$Y$ үшін мүмкін болатын ең үлкен ұзындық бар-жоғын анықтаңыз, ал егер бар болса, сол ең үлкен мәнді табыңыз.

Дұрыс жақшалар тізбегі

Дұрыс жақшалар тізбегі — іргелес () ішкі жолын нөл немесе одан да көп рет қайталап өшіру арқылы бос жолға айналдыруға болатын жол.

Кіріс деректер

Кіріс деректер стандартты енгізуден келесі форматта беріледі:

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

• $N, Q, L_i, R_i$ — бүтін сандар.
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $S$ — тек ( және ) таңбаларынан тұратын ұзындығы $N$ жол.
• $1 \le L_i \le R_i \le N$

Шығыс деректер

$Q$ жол шығарыңыз. $i$-ші жолда $i$-ші сұраныс үшін $Y$ жолының мүмкін болатын ең үлкен ұзындығы бар болса соны, әйтпесе -1 шығарыңыз.

Мысал

1-мысал кіріс

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

1-мысал шығыс

-1
2
0

Ескертпе

• Бірінші сұраныста $X =$ )(. Кез келген оң бүтін $k$ саны үшін, егер $X$ жолының $k$ көшірмесін біріктіріп, бірінші және соңғы таңбаларын өшірсек, ұзындығы $2k - 2$ болатын дұрыс жақшалар тізбегін аламыз. Сондықтан $Y$ үшін мүмкін болатын ең үлкен ұзындық жоқ, сол себепті -1 шығару керек.
• Екінші сұраныста $X =$ ()((. $Y$ жолының мүмкін болатын ең үлкен ұзындығы $2$ екенін дәлелдеуге болады. Сондықтан 2 шығарыңыз.
• Үшінші сұраныста $X =$ ((. $Y$ жолының мүмкін болатын ең үлкен ұзындығы $0$, сондықтан 0 шығарыңыз. $Y$ бос жол болуы мүмкін екеніне назар аударыңыз.