A string $s$ consisting only of ( and ) is defined as a bracket sequence. A valid bracket sequence is defined as follows:

• The empty string is a valid bracket sequence.
• If $A$ and $B$ are both valid bracket sequences, then $A+B$ is also a valid bracket sequence.
• If $A$ is a valid bracket sequence, then $(A)$ is also a valid bracket sequence.

Given a bracket sequence $s$ of length $2n$, modifying the $i$-th bracket has a cost $a_i$. There are $q$ queries, each consisting of modifying $a_i$ and then asking for the minimum cost to transform $s$ into a valid bracket sequence. Modifications are permanent, and queries are independent.

Input

The first line contains two positive integers $n$ and $q$.

The next line contains $2n$ non-negative integers $a_1, \ldots, a_{2n}$.

The next line contains a bracket sequence $s$ of length $2n$.

The next $q$ lines each contain two non-negative integers $i$ and $x$, indicating that $a_i$ is updated to $x$.

Output

Output $q+1$ lines, representing the answer for the initial state and after each modification, respectively.

Examples

Input 1

3 5
9 2 2 2 2 10
())(((
3 7
5 10
6 5
2 2
6 2

Output 1

14
14
14
9
9
6

Input 2

5 10
5 10 6 8 3 6 2 1 16 11
((())()(((
4 9
9 9
2 11
4 20
7 9
1 5
9 16
8 4
2 18
4 20

Output 2

12
12
12
12
12
12
12
12
15
15
15

Examples 3~5

See the provided files.

Constraints

For all data, $1\le n\le 10^5$, $1\le q\le 5\times 10^5$, $0\le a_i, x\le 10^9$, and $s$ is a bracket sequence.

• Subtask 1 (15 pts): $n, q\le 100$
• Subtask 2 (10 pts): $n, q\le 1000$, $s$ is generated randomly among all bracket sequences
• Subtask 3 (10 pts): $n, q\le 1000$
• Subtask 4 (5 pts): $a_i=x=1$
• Subtask 5 (25 pts): $q\le 10^5$
• Subtask 6 (35 pts): No special restrictions