問題文

整合性の取れた括弧列を、ある文字列であって、連続部分文字列 () を選び、それを削除することを $0$ 回以上繰り返して空文字列が得られるものとします。 また、この操作において一回の操作で消される二文字を、互いと整合をとる文字とします。

括弧列 $S$ の $a$ 文字目を $S_a$ とし、$S_a$ と整合を取る文字を $\overline{S_a}$ とします。$\overline{S_a} = S_b$ であるとき $\overline{a} = b$ とします。

例えば、$(())()$ の場合、これは整合が取れていて、例えば $\overline{S_1} = S_4$ です。

整合性の取れた長さ $N$ の括弧列 $S$ が与えられます。

$i(1 \le i \le Q)$ 番目のクエリでは、$S_{x_i}, \overline{S_{x_i}}, S_{y_i}, \overline{S_{y_i}}$ を内部に含む整合をとっている文字のうち、最も内側であるものの index を出力してください。 より形式的には、$ans_i \le x_i, \overline{x_i}, y_i, \overline{y_i} \le \overline{ans_i}$ となる最大の $ans_i$ を求めてください。等号も許容されることに注意してください。 存在しない場合は、$-1$ を出力してください。

制約

• $1 \le N, Q \le 2 \times 10^5$
• $|S| = N$ (ここで $|S|$ は $S$ の長さ)
• $S$ は整合性の取れた括弧列
• $1 \le x_i, y_i \le N$
• $N, Q, x_i, y_i$ はすべて整数

入力

$N\ Q$
$S$
$x_1\ y_1$
$x_2\ y_2$
$\dots$
$x_Q\ y_Q$

出力

$i$ 番目のクエリに対して、$ans_i$ と $\overline {ans_i}$ を昇順で空白区切りで $1$ 行に出力してください。 存在しないケースには $-1$ を出力してください。 合計 $Q$ 行出力してください。最後に改行してください。

サンプル

10 7
(()(()))()
2 4
2 3
2 5
5 7
1 7
1 8
1 10

1 8
2 3
1 8
4 7
1 8
1 8
-1