1140 : Parenthesis

时间限制Time Limit
1 秒Sec
内存限制Memory Limit
128 兆MB
提交次数Submitted
138 次Times
通过次数Solved
28 次Times

题目描述Description

Bobo has a balanced parenthesis sequence P=p1 p2…pn of length n and q questions.

The i-th question is whether P remains balanced after pai and pbi 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 ≤ n ≤ 105, 1 ≤ q ≤ 105).

The second line contains n characters p1 p2…pn.

The i-th of the last q lines contains 2 integers ai,bi (1 ≤ ai, bi ≤ n, ai ≠ bi).

输出格式Output

For each question, output “Yes” if P remains balanced, or “No” otherwise.

样例Sample

出题Author

ftiasch