本題的背景與問題 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$ 可以是空字串。