本题的背景与问题 F 相同。与问题 F 的不同之处用下划线标出。

给定一个长度为 $N$ 且仅由 ( 和 ) 组成的字符串 $S$。

回答 $Q$ 个询问。在第 $i$ 个询问中，给定整数 $L_i$ 和 $R_i$。解决以下问题：

设 $X$ 为 $S$ 从第 $L_i$ 个字符到第 $R_i$ 个字符的子串。考虑选择一个正整数 $k$，然后选择将 $k$ 个 $X$ 拼接得到的字符串的一个子串 $Y$。这里，$Y$ 必须是一个合法括号序列。$Y$ 允许为空字符串。

确定是否存在 $Y$ 的最大可能长度，如果存在，求出该最大值。

合法括号序列

合法括号序列是指可以通过重复删除相邻的子串 () 零次或多次从而缩减为空字符串的字符串。

输入格式

输入从标准输入按以下格式给出：

N Q
S
L1 R1
L2 R2
...
LQ RQ

• $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$，如果我们拼接 $k$ 个 $X$ 并删去第一个和最后一个字符，我们将得到一个长度为 $2k - 2$ 的合法括号序列。因此，$Y$ 不存在最大可能长度，所以你应该输出 -1。
• 在第二个询问中，$X = $ ()((。可以证明 $Y$ 的最大可能长度为 $2$。因此，输出 2。
• 在第三个询问中，$X = $ ((。$Y$ 的最大可能长度为 $0$，所以输出 0。注意 $Y$ 可以是空字符串。