CF1838D.Bracket Walk

There is a string $s$ of length $n$ consisting of the characters '(' and ')'. You are walking on this string. You start by standing on top of the first character of $s$, and you want to make a sequence of moves such that you end on the $n$-th character. In one step, you can move one space to the left (if you are not standing on the first character), or one space to the right (if you are not standing on the last character). You may not stay in the same place, however you may visit any character, including the first and last character, any number of times.

At each point in time, you write down the character you are currently standing on. We say the string is walkable if there exists some sequence of moves that take you from the first character to the last character, such that the string you write down is a regular bracket sequence.

A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence. For example, bracket sequences "()()", "(())" are regular (the resulting expressions are: "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.

One possible valid walk on $s=\mathtt{(())()))}$. The red dot indicates your current position, and the red string indicates the string you have written down. Note that the red string is a regular bracket sequence at the end of the process.

You are given $q$ queries. Each query flips the value of a character from '(' to ')' or vice versa. After each query, determine whether the string is walkable.

Queries are cumulative, so the effects of each query carry on to future queries.

有一个长度为 $n$ 的字符串 $s$，仅由字符 '(' 和 ')' 组成。你将在这个字符串上行走：起始时站在 $s$ 的第一个字符上，目标是通过一系列移动最终停在第 $n$ 个字符上。每一步中，你可以向左移动一格（前提是当前不位于第一个字符处），或向右移动一格（前提是当前不位于最后一个字符处）。你不能原地不动，但可以任意次访问任意字符（包括首字符和末字符）。

在任意时刻，你都会写下当前所站位置的字符。若存在某种从第一个字符走到最后一个字符的移动序列，使得你写下的字符串是一个合法括号序列（regular bracket sequence），则称该字符串是可行走的（walkable）。

合法括号序列是指：可以通过在原序列的字符之间插入字符 '1' 和 '+'，将其转化为一个正确的算术表达式。例如，括号序列 "()()" 和 "(())" 是合法的（对应表达式分别为 "(1)+(1)" 和 "((1+1)+1)"），而 ")(" 和 "(" 则不是。

对 $s=\mathtt{(())()))}$ 的一种可能有效行走方式。红色圆点表示当前位置，红色字符串表示已写下的字符串。注意：在整个过程结束时，该红色字符串是一个合法括号序列。

你将收到 $q$ 个查询。每个查询会将某个位置的字符翻转（即 '(' 变为 ')'，或 ')' 变为 '('）。每次查询后，请判断当前字符串是否可行走。

查询具有累加性，即每个查询的修改效果将持续影响后续所有查询。

The first line of the input contains two integers $n$ and $q$ ($1 \le n, q \le 2\cdot 10^5$) — the size of the string and the number of queries, respectively.

The second line of the input contains a string $s$ of size $n$, consisting of the characters '(' and ')' — the initial bracket string.

Each of the next $q$ lines contains a single integer $i$ ($1\le i \le n$) — the index of the character to flip for that query.

输入的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2\cdot 10^5$），分别表示字符串的长度和查询次数。

输入的第二行包含一个长度为 $n$ 的字符串 $s$，由字符 '(' 和 ')' 组成——即初始的括号字符串。

接下来的 $q$ 行中，每行包含一个整数 $i$（$1\le i \le n$）——表示该次查询中需要翻转的字符的位置索引。

For each query, print "YES" if the string is walkable after that query, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

对于每个查询，如果该查询之后字符串是可遍历的，则输出 “YES”，否则输出 “NO”。

您可以以任意大小写形式输出答案（大写或小写）。例如，字符串 “yEs”、“yes”、“Yes” 和 “YES” 均会被识别为肯定回答。

In the first example:

• After the first query, the string is (())()()(). This string is a regular bracket sequence, so it is walkable by simply moving to the right.
• After the second query, the string is (())()))(). If you move right once, then left once, then walk right until you hit the end of the string, you produce the string (((())()))(), which is a regular bracket sequence.
• After the third query, the string is ()))()))(). We can show that this string is not walkable.

In the second example, the strings after the queries are ()) and ()(, neither of which are walkable.

在第一个例子中：

• 第一次查询后，字符串为 (())()()()。该字符串是一个合法括号序列，因此只需一直向右移动即可遍历。
• 第二次查询后，字符串为 (())()))()。若先向右移动一次，再向左移动一次，然后一直向右走到字符串末尾，则得到字符串 (((())()))()，这是一个合法括号序列。
• 第三次查询后，字符串为 )))()))()。我们可以证明该字符串不可遍历。

在第二个例子中，各次查询后的字符串分别为 ()) 和 ()(，二者均不可遍历。