[JSOI2011]括号序列

内存限制：256 MB 时间限制：2000 ms

JSOI 教练组按如下规则定义配对的括号序列：

例如，以下是配对的括号序列：

(())()()((()()))、((((()))))、()()()()(())

以下则是不配对的括号序列：

)()()()()()(、(())(()、(())(()))()(()

繁多的括号总是让 JSOI 教练组看花眼，难以分辨一个很长的括号序列究竟是不是配对的，所以他请你编写一个程序，输入一个括号序列，并能够完成以下三种操作：

询问将 $A[x]，A[x+1]…A[y]$ 形成的括号序列修改为配对的括号序列，至少需要修改多少个括号。

将 $A[x]，A[x+1]，…A[y]$ 的子序列执行反转，所有的 “（” 修改为 “）”、所有的 “）” 修改为 “（”。

将 $A[x]，A[x+1]，…A[y]$ 的子序列执行翻转，原子序列被 $A[y]，A[y-1]，…A[x]$ 替代。

输入数据的第一行包含两个整数 $N$ 和 $Q$，分别表示括号序列的长度，以及操作的个数。

第二行包含一个长度为 $N$ 的括号序列。

接下来 $Q$ 行，每行三个整数 $t$、$x$ 和 $y$，分别表示操作的类型、操作的开始位置和操作的结束位置，输入数据保证 $x$ 不小于 $y$。其中 $t=0$ 表示询问操作、$t=1$ 表示反转操作、$t=2$ 表示翻转操作。

对于每一个询问操作，输出一行，表示将括号序列的该子序列修改为配对，所需的最少改动个数。

6 3
)(())(
0 1 6
0 1 4
0 3 4

2
2
0

$100\%$ 的数据满足 $N,Q$ 不超过 $10^5$。

C1236 [JSOI2011]括号序列