E2. 猫咪升级（困难版）

每个测试的时间限制：6 秒
内存限制：256 兆字节

本题是困难版。困难版与简单版的唯一区别在于存在删除查询（仅困难版有）。

“星际软件公司”与“塞东尼亚机器人有限公司”共同开发并发布了机器猫。这些电子宠物可以喵喵叫、捉老鼠，并以各种方式娱乐主人。

“星际软件公司”的开发人员最近决定为这些机器人发布一次软件更新。更新后，猫咪必须解决关于括号序列的问题。其中一个问题描述如下。

首先，我们需要了解一些括号序列理论。考虑由字符 "("、")" 和 "." 构成的字符串。如果一个字符串可以通过一次或多次删除操作（每次删除要么删除单个 "." 字符，要么删除一个连续子串 "()"）变成空串，则称该字符串为正则括号序列（RBS）。例如，字符串 "(()(.))" 是一个 RBS，因为可以通过以下删除序列变成空串：

"(()(.))" → "(()())" → "(())" → "()" → ""

我们得到了空串，所以初始字符串是 RBS。同时，字符串 ")(" 不是 RBS，因为无法对它应用这样的删除操作。

如果一个 RBS 非空，不以 "." 开头，也不以 "." 结尾，则称它是简单 RBS。

记字符串 $s$ 的子串为其连续的一段。特别地，$s[l\ldots r] = s_l s_{l+1} \ldots s_r$，其中 $s_i$ 是字符串 $s$ 的第 $i$ 个字符。

现在回到问题描述本身。给你一个字符串 $s$，初始由字符 "(" 和 ")" 组成。你需要回答以下查询：

1. 给定两个下标 $l$ 和 $r$（$1 \le l < r \le n$）。保证第 $l$ 个字符是 "("，第 $r$ 个字符是 ")"，且它们之间的字符都是 "."。然后需要将第 $l$ 个和第 $r$ 个字符设置为 "."。
2. 给定两个下标 $l$ 和 $r$（$1 \le l < r \le n$），并保证子串 $s[l\ldots r]$ 是一个简单 RBS。你需要求出 $s[l\ldots r]$ 中有多少个子串是简单 RBS。换句话说，求满足 $l \le i < j \le r$ 且 $s[i\ldots j]$ 是简单 RBS 的二元组 $(i, j)$ 的数量。

你是“星际软件公司”的一名员工，被分配了任务：教猫咪在升级后解决上述问题。

输入

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 3 \cdot 10^5$，$1 \le q \le 3 \cdot 10^5$），分别表示字符串的长度和查询的数量。

第二行包含字符串 $s$，由 $n$ 个字符 "(" 和 ")" 组成。

接下来的 $q$ 行，每行包含三个整数 $t$、$l$ 和 $r$（$t \in \{1, 2\}$，$1 \le l < r \le n$），表示需要回答的查询。保证所有查询都是合法的，且符合问题描述中的条件。

输出

对于每个查询，输出一行一个整数，即简单 RBS 子串的数量。输出的顺序与输入中查询的顺序相同。

示例

输入

9 8
)(()())()
2 3 6
2 2 7
1 3 4
2 2 7
2 2 9
1 5 6
1 2 7
2 8 9

输出

3
4
2
4
1

说明

考虑示例测试用例。

• 第一个查询的答案是 $3$，因为有 $3$ 个符合条件的子串：$s[3\ldots 6]$、$s[3\ldots 4]$ 和 $s[5\ldots 6]$。
• 第二个查询的答案是 $4$。这些子串是 $s[3\ldots 6]$、$s[3\ldots 4]$、$s[5\ldots 6]$ 和 $s[2\ldots 7]$。
• 第三个查询之后，字符串变为 ")(..())()"。
• 第四个查询的答案是 $2$。这些子串是 $s[5\ldots 6]$ 和 $s[2\ldots 7]$。注意 $s[3\ldots 6]$ 不再是简单 RBS，因为它以 "." 开头。
• 第五个查询的答案是 $4$。这些子串是 $s[5\ldots 6]$、$s[2\ldots 7]$、$s[8\ldots 9]$ 和 $s[2\ldots 9]$。
• 第六个查询之后，字符串变为 ")(....)()"。
• 第七个查询之后，字符串变为 ")......()"。
• 第八个查询的答案是 $1$。这个子串是 $s[8\ldots 9]$。