Bobo has a balanced parenthesis sequence $P = p_1p_2\dots p_n$ of length $n$ and $q$ questions.

The $i$-th question is whether $P$ remains balanced after $p_{a_i}$ and $p_{b_i}$ swapped. Note that questions are individual so that they have no affect on others.

Parenthesis sequence $S$ is balanced if and only if:

1. $S$ is empty;
2. or there exists balanced parenthesis sequence $A, B$ such that $S = AB$;
3. or there exists balanced parenthesis sequence $S'$ such that $S = (S')$.

Input

The input contains at most $30$ sets. For each set:

The first line contains two integers $n, q$ ($2 \leq n \leq 10^5, 1 \leq q \leq 10^5$).

The second line contains $n$ characters $p_1p_2\dots p_n$.

The $i$-th of the last $q$ lines contains $2$ integers $a_i, b_i$ ($1 \leq a_i, b_i \leq n, a_i \neq b_i$).

Output

For each question, output "Yes" if $P$ remains balanced, or "No" otherwise.

Sample Input

4 2
(())
1 3
2 3
2 1
()
1 2

Sample Output

No
Yes
No