この問題の設定は問題 F と同じです。問題 F との相違点には下線が引かれています。

( と ) のみからなる長さ $N$ の文字列 $S$ が与えられます。

$Q$ 個のクエリに答えてください。$i$ 番目のクエリでは、整数 $L_i$ と $R_i$ が与えられます。次の問題を解いてください：

$S$ の $L_i$ 文字目から $R_i$ 文字目までの部分文字列を $X$ とします。正の整数 $k$ を選び、$X$ を $k$ 個連結して得られる文字列の部分文字列 $Y$ を選ぶことを考えます。ここで、$Y$ は正しい括弧列でなければなりません。$Y$ は空文字列であっても構いません。

$Y$ の長さとしてあり得る最大値が存在するかどうかを判定し、存在する場合はその最大値を求めてください。

正しい括弧列

正しい括弧列とは、連続する部分文字列 () を $0$ 回以上繰り返し削除することで空文字列にできる文字列のことです。

入力

入力は以下の形式で標準入力から与えられます：

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

注記

• $1$ 番目のクエリでは、$X =$ )( です。任意の正の整数 $k$ に対して、$X$ を $k$ 個連結して先頭と末尾の文字を取り除くと、長さ $2k - 2$ の正しい括弧列が得られます。したがって、$Y$ の長さの最大値は存在しないため、-1 を出力します。
• $2$ 番目のクエリでは、$X =$ ()(( です。$Y$ の長さの最大値は $2$ であることが証明できます。したがって、2 を出力します。
• $3$ 番目のクエリでは、$X =$ (( です。$Y$ の長さの最大値は $0$ であるため、0 を出力します。$Y$ は空文字列でもよいことに注意してください。