本題嘅背景同問題 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
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$，如果我哋拼接 $k$ 個 $X$ 並刪走頭尾字元，就可以得到一個長度為 $2k - 2$ 嘅合法括號序列。因此，$Y$ 唔存在最大可能長度，所以你應該輸出 -1。
• 喺第二個詢問入面，$X =$ ()((。可以證明 $Y$ 嘅最大可能長度係 $2$。因此，輸出 2。
• 喺第三個詢問入面，$X =$ ((。$Y$ 嘅最大可能長度係 $0$，所以輸出 0。注意 $Y$ 可以係空字串。