括号序列是由左括号和右括号组成的序列。当且仅当满足以下两个条件时，称一个括号序列是平衡的：

• 它包含相等数量的左括号和右括号；
• 对于每一个前缀，右括号的数量不大于左括号的数量。

如果一个括号序列包含相等数量的左括号和右括号，且不是平衡的，则称其为“叛逆的”（rebellious）。

给定一个长度为 $n$ 的平衡括号序列和 $q$ 次查询。每次查询要求交换两个括号。保证每次查询后序列仍然保持平衡。

在每次查询后，你需要判断是否可以将该序列拆分为若干个不相交的“叛逆的”子序列。

形式化地，设原序列为 $s_1s_2 \dots s_n$。你需要检查是否存在一个数字 $k > 1$（子序列的数量）以及 $k$ 个非空下标序列 $(i_{1,1} < \dots < i_{1,l_1}), \dots, (i_{k,1} < \dots < i_{k,l_k})$，使得对于每个 $1 \le j \le k$，括号序列 $s_{i_{j,1}}s_{i_{j,2}} \dots s_{i_{j,l_j}}$ 都是“叛逆的”，且 $1$ 到 $n$ 之间的每个整数在这些序列中恰好出现一次。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 300\,000$)，分别表示序列的长度和查询次数。第二行是一个长度为 $n$ 的字符串，由字符 '(' 和 ')' 组成。

接下来 $q$ 行描述查询。每行包含两个整数 $i$ 和 $j$ ($1 \le i < j \le n$)，表示交换第 $i$ 个和第 $j$ 个位置上的括号。

保证序列初始时是平衡的，且在每次查询后仍然保持平衡。

输出格式

在每次查询后，如果可以将序列拆分为若干个不相交的“叛逆的”子序列，则输出 “Yes”，否则输出 “No”。

样例

输入 1

8 4
(()()())
3 4
5 6
2 7
6 7

输出 1

No
No
Yes
No