Ryan 对仅由 '(' 和 ')' 组成的字符串很感兴趣。特别地，他非常喜欢平衡括号串。任何平衡括号串都可以根据以下规则构造：

• 字符串 "()" 是平衡的。
• 两个平衡括号串的拼接是平衡的。
• 如果 $T$ 是一个平衡括号串，则按顺序拼接 '(', $T$, 和 ')' 得到的字符串也是平衡的。

例如，"()()" 和 "(()())" 是平衡括号串。")(", ")(()()" 和 "(" 不是平衡括号串。

我们定义字符串 $T$ 的 Ryan 挫败度为通过以下操作（可以以任意顺序执行任意次数）将 $T$ 变为平衡括号串所需的最少操作次数：

• 在 $T$ 的开头添加 ')'。
• 在 $T$ 的末尾添加 '('。
• 交换 $T$ 中相邻的两个字符。

Ryan 有一个长度为 $N$ 的字符串 $S$，仅由 '(' 和 ')' 组成。给定 $Q$ 次查询，按顺序处理它们。查询有两种格式：

• $1\ l\ r$：对于 $S$ 中从第 $l$ 个到第 $r$ 个（包含第 $r$ 个）的每个字符，如果它是 '('，则将其替换为 ')'；如果它是 ')'，则将其替换为 '('。
• $2\ l\ r$：输出 $S$ 中从第 $l$ 个到第 $r$ 个字符组成的子串的 Ryan 挫败度。

输入格式

第一行包含两个整数 $N$ 和 $Q$ ($2 \le N \le 150\,000, 1 \le Q \le 150\,000$)，用空格分隔，分别表示字符串 $S$ 的长度和查询次数。下一行包含字符串 $S$，仅由 '(' 和 ')' 组成，长度为 $N$。接下来的 $Q$ 行，每行包含三个整数 $t_i, l_i$ 和 $r_i$ ($1 \le t_i \le 2, 1 \le l_i \le r_i \le N$)，用空格分隔，表示第 $i$ 次查询。

保证至少存在一次 $t_i = 2$ 的查询。

输出格式

对于每次 $t_i = 2$ 的查询，输出 Ryan 的挫败度，并换行。

样例

样例输入 1

6 6
())()(
2 1 6
1 2 4
2 1 4
2 2 5
1 1 5
2 1 6

样例输出 1

2
5
0
6

样例输入 2

7 5
(((((()
2 1 7
1 1 7
2 1 7
2 3 3
2 2 6

样例输出 2

20
26
2
20