J. 括号序列
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

合法的括号序列定义如下：

  • "()" 是一个合法的括号序列。
  • 若 "A" 是一个合法的括号序列，则 "(A)" 也是一个合法的括号序列。
  • 若 "A", "B" 是一个合法的括号序列，则 "AB" 也是一个合法的括号序列。
  • 比如，"((())())" 是一个合法的括号序列，")()(" 不是一个合法的括号序列。

现给出一个长度为 n 的合法的括号序列 S，以及 m 个区间括号变更操作。

区间 l, r 的括号变更操作，会将当前维护的括号序列中，第 l 到 r 个括号进行修改，将这一段中的左括号 "(" 更改为右括号 ")"，同时右括号 ")" 更改为左括号 "("。

操作以最初给定的括号序列作为当前维护的括号开始进行，按顺序对当前维护的括号序列进行修改。

请在每次操作之后，判断修改后的序列是否是合法的括号序列。

Input

第一行，两个整数 n, m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105)，保证 n 为偶数，分别表示括号序列的长度和操作的数量。

第二行，一个长度为 n 的合法的括号序列 S。

接下来 m 行，每行两个整数 lj, rj (1 ≤ lj ≤ rj ≤ n)，其中的第 j 行表示第 j 次操作的参数，进行题目所描述的操作。

Output

输出 m 行，每行为字符串 yes 或 no，大小写不敏感。

若第 j 个输出为 yes，则表示按顺序进行完第 j 个操作后，括号序列合法；若第 j 个输出为 no，则表示按顺序进行完第 j 个操作后，括号序列不合法。

Examples
Input
4 8
(())
2 3
2 3
2 4
2 2
3 4
1 2
3 4
1 4
Output
yeS
YeS
no
no
yEs
no
NO
yeS
Input
8 12
((()()))
4 5
6 7
1 6
2 7
1 2
4 7
5 8
2 6
1 5
1 2
7 8
2 8
Output
yeS
No
no
no
yEs
yes
NO
NO
No
nO
YeS
No
Note

在第一个样例中，操作后的括号序列如下表：