猫咪升级（简单版）

• 时间限制：5 秒
• 内存限制：256 MiB

题目背景

这是本题的简单版本。本版本只有查询，没有困难版中的删除操作。

题目描述

正规括号序列（RBS）是能够按通常规则正确匹配的括号序列。在本版本中字符串只含 ( 和 )，因此非空正规括号序列就是“简单 RBS”。

给定一个只含左右括号的字符串 $s$。每次查询给出 $l,r$，并保证 $s[l\dots r]$ 是简单 RBS。请计算这个区间中有多少个子串也是简单 RBS，即满足 $l\le i<j\le r$ 且 $s[i\dots j]$ 为 RBS 的下标对 $(i,j)$ 数量。

输入格式

第一行包含两个整数 $n,q$，分别表示字符串长度和查询数。

第二行是长度为 $n$ 的字符串 $s$。

接下来 $q$ 行，每行包含三个整数 $t,l,r$。本版本中 $t=2$，并保证查询区间合法且 $s[l\dots r]$ 是简单 RBS。

输出格式

对每个查询输出一行一个整数，表示答案。

样例输入

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

样例输出

3
4
1
6

数据范围

对所有数据，$2\le n\le3\times10^5$，$1\le q\le3\times10^5$，$s$ 只含 ( 和 )，且所有查询均符合题目保证。