F. Bracket Distance
time limit per test
2.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

有一个长度为$$$n$$$的括号序列$$$seq$$$，序列下标从$$$1$$$开始，你需要从中选择一个子序列，该子序列需要满足： 1. 该序列是一个匹配的括号序列。 2. 该序列中没有出现多层括号嵌套的情况。 例如'(())'中就出现了一个两层括号嵌套的情况，是不满足条件的，但是'()()()'就是一个满足条件的括号序列。

假设选出的括号序列$$$s$$$长度为$$$len$$$，$$$index_i$$$表示序列中第$$$i$$$个括号在原序列中的下标，那么这个括号序列的优美度为： $$$$$$ \sum_{i=1}^{len} index_i·[s_i = ')'] - \sum_{i=1}^{len} index_i·[s_i = '('] $$$$$$

其中'"[]"'内的内容代表需要满足的条件，即你选择的子括号序列中所有右括号在原序列中的下标和减去所有左括号在原序列中的下标和。

现在有$$$q$$$次修改操作: 'pos c'，即 $$$seq_{pos} := c$$$ 。

你需要在每次修改操作后输出一个整数，代表在这次修改后你能取出的优美度最大的合法子序列的优美度。

请注意，每次修改操作会实际地修改括号序列。

Input

第一行，两个整数 $$$n,q(1\le n \le 2·10^5;1\le q \le 2·10^5)$$$代表初始时括号序列的长度和修改操作的次数。

第二行，一个长度为$$$n$$$括号序列，不保证该括号序列是匹配的括号序列。

接下来连续的$$$q$$$行，每行两个整数 $$$pos,c(1\le pos\le n;c是左括号或右括号)$$$，代表一次操作。

Output

共$$$q$$$行，在每次操作后能输出可以取出的合法的优美度最大的子序列的优美度，如果取不出任何的合法的子序列，输出'0'。

Example
Input
5 2
())))
1 )
2 (
Output
0
3
Note

第一次修改后，括号序列变为')))))'，选不出任何合法子序列。 第二次修改后，括号序列变为')()))'，选择下标$$$2$$$和$$$5$$$的括号作为当前子序列。