codeforces#P1625E1. Cats on the Upgrade (easy version)

    ID: 32650 远端评测题 6000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>brute forcedata structuresdfs and similardivide and conquerdpgraphstrees

Cats on the Upgrade (easy version)

Description

This is the easy version of the problem. The only difference between the easy and the hard versions are removal queries, they are present only in the hard version.

"Interplanetary Software, Inc." together with "Robots of Cydonia, Ltd." has developed and released robot cats. These electronic pets can meow, catch mice and entertain the owner in various ways.

The developers from "Interplanetary Software, Inc." have recently decided to release a software update for these robots. After the update, the cats must solve the problems about bracket sequences. One of the problems is described below.

First, we need to learn a bit of bracket sequence theory. Consider the strings that contain characters "(", ")" and ".". Call a string regular bracket sequence (RBS), if it can be transformed to an empty string by one or more operations of removing either single "." characters, or a continuous substring "()". For instance, the string "(()(.))" is an RBS, as it can be transformed to an empty string with the following sequence of removals:

"(()(.))" \rightarrow "(()())" \rightarrow "(())" \rightarrow "()" \rightarrow "".

We got an empty string, so the initial string was an RBS. At the same time, the string ")(" is not an RBS, as it is not possible to apply such removal operations to it.

An RBS is simple if this RBS is not empty, doesn't start with ".", and doesn't end with ".".

Denote the substring of the string ss as its sequential subsegment. In particular, s[lr]=slsl+1srs[l\dots r] = s_ls_{l+1}\dots s_r, where sis_i is the ii-th character of the string ss.

Now, move on to the problem statement itself. You are given a string ss, initially consisting of characters "(" and ")". You need to answer the queries of the following kind.

Given two indices, ll and rr (1l<rn1 \le l < r \le n), and it's guaranteed that the substring s[lr]s[l\dots r] is a simple RBS. You need to find the number of substrings in s[lr]s[l\dots r] such that they are simple RBS. In other words, find the number of index pairs ii, jj such that li<jrl \le i < j \le r and s[ij]s[i\dots j] is a simple RBS.

You are an employee in "Interplanetary Software, Inc." and you were given the task to teach the cats to solve the problem above, after the update.

Note that the "." character cannot appear in the string in this version of the problem. It is only needed for the hard version.

The first line contains two integers nn and qq (2n31052 \le n \le 3\cdot10^5, 1q31051 \le q \le 3\cdot10^5), the length of the string, and the number of queries.

The second line contains the string ss, consisting of nn characters "(" and ")".

Each of the following qq lines contains three integers tt, ll and rr (t=2t = 2, 1l<rn1 \le l < r \le n), the queries you need to answer. It is guaranteed that all the queries are valid and correspond to the problem statements. Note that tt is unused and always equal to two in this problem. It is required for the hard version of the problem.

For each query, print a single integer in a separate line, the number of substrings that are simple RBS. The answers must be printed in the same order as the queries are specified in the input.

Input

The first line contains two integers nn and qq (2n31052 \le n \le 3\cdot10^5, 1q31051 \le q \le 3\cdot10^5), the length of the string, and the number of queries.

The second line contains the string ss, consisting of nn characters "(" and ")".

Each of the following qq lines contains three integers tt, ll and rr (t=2t = 2, 1l<rn1 \le l < r \le n), the queries you need to answer. It is guaranteed that all the queries are valid and correspond to the problem statements. Note that tt is unused and always equal to two in this problem. It is required for the hard version of the problem.

Output

For each query, print a single integer in a separate line, the number of substrings that are simple RBS. The answers must be printed in the same order as the queries are specified in the input.

Samples

输入数据 1

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

输出数据 1

3
4
1
6

Note

Consider the example test case.

The answer to the first query is 33, as there are three suitable substrings: s[36]s[3\dots6], s[34]s[3\dots4] and s[56]s[5\dots6].

The answer to the second query is 44. The substrings are s[36]s[3\dots6], s[34]s[3\dots4], s[56]s[5\dots6] and s[27]s[2\dots7].

The answer to the third query is 11. The substring is s[89]s[8\dots9].

The answer to the fourth query is 66. The substrings are s[36]s[3\dots6], s[34]s[3\dots4], s[56]s[5\dots6], s[27]s[2\dots7], s[89]s[8\dots9] and s[29]s[2\dots9].