Problem Statement

A well-formed bracket sequence is a string from which the empty string can be obtained by repeating, $0$ or more times, the operation of choosing a contiguous substring () and deleting it. Also, the two characters deleted in a single such operation are said to match each other.

Let $S_a$ be the $a$-th character of a bracket sequence $S$, and let $\overline{S_a}$ be the character that matches $S_a$. When $\overline{S_a} = S_b$, we define $\overline{a} = b$.

For example, $(())()$ is well-formed, and for instance $\overline{S_1} = S_4$.

You are given a well-formed bracket sequence $S$ of length $N$.

In the $i(1 \le i \le Q)$-th query, output the index of the innermost pair of matching characters that contains $S_{x_i}, \overline{S_{x_i}}, S_{y_i}, \overline{S_{y_i}}$ inside it. More formally, find the maximum $ans_i$ such that $ans_i \le x_i, \overline{x_i}, y_i, \overline{y_i} \le \overline{ans_i}$. Note that equality is allowed. If no such pair exists, output $-1$.

Constraints

• $1 \le N, Q \le 2 \times 10^5$
• $|S| = N$ (where $|S|$ is the length of $S$)
• $S$ is a well-formed bracket sequence
• $1 \le x_i, y_i \le N$
• $N, Q, x_i, y_i$ are all integers

Input

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

Output

For the $i$-th query, output $ans_i$ and $\overline {ans_i}$ in ascending order, separated by a space, on $1$ line. If no such pair exists, output $-1$. Output $Q$ lines in total. Print a newline at the end.

Sample

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