Flipping Parentheses

A string made only of ( and ) is called balanced if it satisfies one of the following conditions.

• The string () is balanced.
• The concatenation of two balanced strings is balanced.
• If a string $s$ is balanced, then the concatenation of (, $s$, and ) in this order is balanced.

This condition is stronger than requiring equal counts of ( and ). For example, ())(() has three of each but is not balanced.

Your task is to keep a string balanced in a harsh setting where a cosmic ray may flip the direction of a parenthesis.

You are given a balanced string at the start. Each time the direction of a single parenthesis is flipped, your program is told the position of the changed character. You then compute and output the leftmost position such that flipping the parenthesis there makes the whole string balanced again. After the string is balanced by flipping the parenthesis your program reported, the next cosmic ray flips another parenthesis, and the same steps repeat several times.

The input consists of a single test case in the following format.

N Q
s
q1
.
.
.
qQ

The first line contains two integers $N$ and $Q$ ($2 \le N \le 300000$, $1 \le Q \le 150000$). The second line contains a balanced parenthesis string $s$ of length $N$. Each of the following $Q$ lines contains an integer $q_i$ ($1 \le q_i \le N$), which means that the direction of the $q_i$-th parenthesis is flipped.

For each event $q_i$, output on its own line the leftmost position of a parenthesis you have to flip to get back to the balanced state. Such a position always exists.

Each event $q_i$ applies to the string after the previous event $q_{i-1}$ and its fix.

In the first example the initial state is ((())). The 4th parenthesis is flipped and the string becomes (((()). To restore the balance you flip the 2nd parenthesis and get ()(()). The next flip, of the 3rd parenthesis, applies to that last state and yields ())()). Changing the 2nd parenthesis once more gives (()()), which is balanced.