E. RBS Score
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You have been given a bracket sequence $$$s_1 s_2 \dots s_n$$$ of length $$$n$$$. The score of the sequence $$$s$$$ is the number of pairs $$$(l,r)$$$ such that $$$1 \leq l \leq r \leq n$$$ and $$$s_l s_{l+1} \dots s_r$$$ forms a regular bracket sequence$$$^\dagger$$$.

There are $$$q$$$ operations which will be performed on $$$s$$$. The $$$i$$$-th operation is described as follows:

  • Swap the $$$p_i$$$-th character with the $$$(p_i+1)$$$-th character in $$$s$$$. The effect of this operation is permanent, meaning that the sequence $$$s$$$ is permanently modified after this operation.

For each $$$i$$$ such that $$$1 \leq i \leq q$$$, calculate the score of $$$s$$$ after the $$$i$$$-th operation is performed.

$$$^\dagger$$$A regular bracket sequence is a bracket sequence where if we add + and 1 into the sequence, it is possible for us to get a correct mathematical expression. For example, (), ((())), and ()(()) are all regular bracket sequences, while )(, ((), and ())(()() are not.

Input

The first line contains two integers $$$n,q$$$ ($$$2 \leq n \leq 2 \cdot 10^5, 1 \leq q \leq 2 \cdot 10^5$$$) — the length of the bracket sequence and the number of operations performed.

The second line contains a bracket sequence $$$s$$$ of length $$$n$$$. For each $$$i$$$ such that $$$1 \leq i \leq n$$$, $$$s_i$$$ is either ( or ).

The third line contains $$$q$$$ integers $$$p_1,p_2,\dots,p_q$$$ ($$$1 \leq p_i \lt n$$$) — the operations described in the statement.

Output

Output $$$q$$$ integers $$$c_1,c_2,\dots,c_q$$$ separated by spaces. For each $$$i$$$ such that $$$1 \leq i \leq q$$$, $$$c_i$$$ represents the score of $$$s$$$ after the $$$i$$$-th operation is performed.

Example
Input
6 4
((()))
3 2 4 1
Output
4 4 6 3
Note

After the first operation, $$$s=$$$(()()). There are $$$4$$$ number of pairs $$$(l,r)$$$ such that $$$s_l s_{l+1} \dots s_r$$$ forms a regular bracket sequence, which are $$$(1,6), (2,3), (2,5), (4,5)$$$. Thus, the score of $$$s$$$ after the first operation is $$$4$$$.

After the second operation, $$$s=$$$()(()). The score of $$$s$$$ after this operation is $$$4$$$.

After the third operation, $$$s=$$$()()(). The score of $$$s$$$ after this operation is $$$6$$$.

After the fourth operation, $$$s=$$$)(()(). The score of $$$s$$$ after this operation is $$$3$$$.