#P18005. Greatest Bracket Sequence

Greatest Bracket Sequence

Greatest Bracket Sequence

给定一个长度为 NN、仅含 ( 和 ) 的字符串 SS。

回答 QQ 次询问。每次给定 Li,RiL_i,R_i,令 X=S[Li…Ri]X=S[L_i\ldots R_i]。可以任意选择一个正整数 kk,将 kk 个 XX 连接起来,再从连接后的字符串中选择一个连续子串 YY,要求 YY 是合法括号序列。允许 YY 为空串。

判断 YY 的长度是否存在最大值。若存在,输出最大长度;否则输出 −1-1。

合法括号序列指能通过反复删除连续子串 (),最终变成空串的字符串。删除次数可以为零。

输入格式

第一行两个整数 N,QN,Q。第二行字符串 SS。接下来 QQ 行,每行两个整数 Li,RiL_i,R_i。字符串下标从 11 开始。

输出格式

输出 QQ 行,每行给出对应询问的最大长度;若长度无上界则输出 -1。

数据范围

1≤N,Q≤2×1051\le N,Q\le2\times10^5,1≤Li≤Ri≤N1\le L_i\le R_i\le N。∣S∣=N|S|=N,且 SS 只含两种括号。

样例 1

输入

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

输出

-1
2
0