Parentheses Subsequence Operations

You are given a string \(S\) of length \(n\) consisting only of the characters ( and ).

You will perform \(m\) operations on the string. There are two types of operations:

• 1 l r: For all indices \(i\) with \(l \le i \le r\), flip the parenthesis, i.e. change ( to ) and ) to (.
• 2 l r: For the subarray \(S[l, r]\), compute \(\displaystyle \frac{L}{2}\) where \(L\) is the length of the longest valid parentheses subsequence in \(S[l, r]\). (Note that a subsequence is a sequence of indices \(1 \le i_1 < i_2 < \cdots < i_k \le n\) and a valid parentheses sequence is defined recursively as: an empty sequence is valid; if \(A\) is valid then \((A)\) is valid; if \(A\) and \(B\) are valid then the concatenation \(AB\) is also valid.)

Note: A valid parentheses subsequence is not necessarily contiguous. In other words, you are allowed to remove some characters (possibly none) while preserving the order, so that the remaining sequence is a valid parentheses sequence. The answer for a query is the number of matched pairs in the subsequence.

Hint: You may observe that if you can compute the maximum number of matched pairs \(P\) in a segment, then the answer to a query is \(P\) (since the longest valid subsequence has length \(2P\), and after dividing by \(2\) we get \(P\)).

It is guaranteed that the input operations are valid.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le n, m \le 2\times10^5)\) --- the length of the string and the number of operations.

The second line contains the string \(S\) of length \(n\), which consists only of characters ( and ).

The next \(m\) lines each describe an operation in one of the two forms:

• 1 l r
• 2 l r

For each operation, \(1 \le l \le r \le n\).

outputFormat

For each operation of the second type, output a single integer on a new line --- the answer to the query.

sample

8 5
(()())()
2 1 8
1 3 6
2 1 8
1 1 8
2 1 8

4
2
1