有一个长度为 $$$n$$$ 的字符串 $$$s$$$,由字符“(”和“)”组成。你正走在这根绳子上。首先,您站在 $$$s$$$ 的第一个字符之上,并且您想要进行一系列移动,以便在第 $$$n$$$ 个字符上结束。在一步中,您可以向左移动一个空格(如果您没有站在第一个字符上),也可以向右移动一个空格(如果您没有站在最后一个字符上)。您可能不会停留在同一个地方,但是您可以多次访问任何角色,包括第一个和最后一个角色。
在每个时间点,你写下你当前站立的角色。如果存在一些从第一个字符到最后一个字符的移动序列,使得您写下的字符串是常规的括号序列,我们就说该字符串是可步行的。
常规括号序列是通过在序列的原始字符之间插入字符“1”和“+”可以将括号序列转换为正确的算术表达式。例如,括号序列“()()”、“(())”是正则表达式(结果表达式为:“(1)+(1)”、“((1+1)+1)”),而“)(”和“(”则不是。
$$$s=\mathtt{(())()))}$$$ 上的一个可能的有效步行。红点表示您当前的位置,红色字符串表示您写下的字符串。请注意,红色字符串是过程末尾的常规括号序列。
您收到 $$$q$$$ 查询。每个查询都会将字符的值从“(”翻转到“)”,反之亦然。每次查询后,确定字符串是否可步行。
查询是累积的,因此每个查询的影响都会延续到未来的查询。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2\cdot 10^5$$$) - 分别是字符串的大小和查询的数量。
输入的第二行包含一个大小为 $$$n$$$ 的字符串 $$$s$$$,由字符“(”和“)”组成 - 初始括号字符串。
接下来的 $$$q$$$ 行都包含一个整数 $$$i$$$ ($$$1\le i \le n$$$) — 针对该查询要翻转的字符的索引。
输出
对于每个查询,如果该查询之后的字符串可步行,则打印“YES”,否则打印“NO”。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。
示例
输入 #1
10 9 (())()())) 9 7 2 6 3 6 7 4 8
输出 #1
YES YES NO NO YES NO YES NO NO
输入 #2
3 2 (() 2 3
输出 #2
NO NO
注意
在第一个示例中:
- 第一次查询后,字符串为 (())()()()。该字符串是一个常规的括号序列,因此只需向右移动即可遍历它。
- 第二次查询后,字符串为 (())()))()。如果向右移动一次,然后向左移动一次,然后向右移动直到到达字符串末尾,则会生成字符串 (((())()))(),这是一个常规的括号序列。
- 第三次查询后,字符串为 ()))()))()。我们可以证明这个字符串是不可走的。