You have a string $s$ of length $n$, consisting of characters "$($" and "$)$". There are two types of query:

•  $1 \ l \ r$ — $(Type\ 1)$ Flip the parentheses $($i.e. replace each parenthesis with its opposite$)$ at all positions with indices from $l$ to $r,$ both inclusive: each character '$($' is replaced with '$)$' and each character '$)$' is replaced with '$($' $(1 \leq l \leq r \leq n);$
• $2 \ l \ r$ — $(Type\ 2)$ Find the length of the maximum correct bracket subsequence of sequence $s_l, s_{l+1},....,s_{r}.$

A subsequence of length $|x|$ of string $s = s_1s_2...s_{|s|}$ $($where $|s|$ is the length of string $s)$ is string $x = s_{k_1}s_{k_2}... s_{k_{|x|}} \ (1 \leq k_1 < k_2 < ... < k_{|x|} \leq |s|)$.

A correct bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "$1$" and "$+$" between the characters of the string. For example, bracket sequences "$()()$", "$(())$" are correct $($the resulting expressions "$(1)+(1)$", "$((1+1)+1)$"$)$, and "$)($" and "$($" are not.

Input:

The first line contains two integers $n$ and $m$ — the length of the string $s$ and the number of queries correspondingly. The next line contains a sequence of characters $s_1,s_2,..., s_n$  without any spaces. Each character is either a "$($" or a "$)$". Each of the next $m$ lines contains a number that denotes the type of the query followed by a pair of integers. The $i-th$ line contains integers $t, l,r$ — the description of the $i-th$ query.

Output:

For each query of type 2 print the required answer on a new line.

Constraints:

• $1 \leq n \leq 10^6$
• $1 \leq m \leq 3\times 10^5$
• $1 \leq t \leq 2$
• $1 \leq l \leq r \leq n$