问题文

高桥君是一个「装酷」的人。他喜欢在由开括号(和闭括号)组成的字符串中插入或删除括号。每个字符串都有一个定义为「括号难看度」的值。要使一个字符串 $S$ 变得「完美」，需要删除的字符数的最小值就是它的「括号难看度」。如果括号的配对没有矛盾，那么这个字符串就是「完美」的。尤其是，空串也是「完美」的。

例如，字符串 ()()(()) 是「完美」的，它的「括号难看度」为 $0$。 ()) 如果移除最后一个括号，就变成了「完美」的。因此，它的「括号难看度」是 $1$。

高桥君从朋友那里获得了一个字符串 $S$。现在他要在这个字符串中插入或删除括号。高桥君有时会关注字符串中某一部分的「括号难看度」。您需要在高桥君问及「括号难看度」时计算出它。

---

输入

输入由标准输入给出，具体格式如下：

$Q$ $S$ $x_1$ $y_1$ $z_1$ $x_2$ $y_2$ $z_2$ : $x_Q$ $y_Q$ $z_Q$

• 第 $1$ 行为高桥君操作的次数 $Q (1 ≦ Q ≦ 10^5)$。
• 第 $2$ 行为高桥君获得的字符串 $S (1 ≦ | S | ≦ 10^5)$。
• 接下来的 $Q$ 行，第 $i$ 行为第 $i$ 个操作内容，由字符 $x_i$ 和数字 $y_i, z_i$ 组成，以空格分隔。
• 当 $x_i$ 为 ( 时，表示插入开括号操作，在位置 $y_i$ 处插入开括号，此时 $z_i$ 始终为 $0$。
• 当 $x_i$ 为 ) 时，表示插入闭括号操作，在位置 $y_i$ 处插入闭括号，此时 $z_i$ 始终为 $0$。
• 当 $x_i$ 为 D 时，表示删除操作，删除位置 $y_i$ 处的字符，此时 $z_i$ 始终为 $0$。
• 当 $x_i$ 为 Q 时，表示提问操作，在位置 $y_i$ 到 $z_i$ 的范围内（包括两端）询问「括号难看度」。
• 没有删除不存在的字符，提问不存在的范围，插入字符到不存在的位置的输入。此外，所有位置皆基于 1 索引。

---

输出

输出由多行组成。每当高桥君提问时，输出其答案。

---

输入示例1

5
(()
D 1 0
( 3 0
Q 1 2
) 1 0
Q 2 4

输出示例1

0
1

第 $1$ 次操作结束后的状态为 ()

第 $2$ 次操作结束后的状态为 ())

第 $3$ 次操作被询问的范围的字符串为 ()

第 $4$ 次操作结束后的状态为 (())

第 $5$ 次操作被询问的范围的字符串为 ())

---

输入示例2

11
(()()(()
( 1 0
( 1 0
D 4 0
Q 2 6
) 5 0
D 8 0
Q 1 9
( 3 0
) 8 0
D 10 0
Q 5 10

输出示例2

1
1
4

第 $1$ 次操作结束后的状态为 ((()()(()

第 $2$ 次操作结束后的状态为 (((()()(()

第 $3$ 次操作结束后的状态为 ((()()(()

第 $4$ 次操作被询问的范围的字符串为 (()()

第 $5$ 次操作结束后的状态为 ((())()(()

第 $6$ 次操作结束后的状态为 ((())()()

第 $7$ 次操作被询问的范围的字符串为 ((())()()

第 $8$ 次操作结束后的状态为 (((())()()

第 $9$ 次操作结束后的状态为 (((())())()

第 $10$ 次操作结束后的状态为 (((())()))

第 $11$ 次操作被询问的范围的字符串为 `))())))