Problem Statement

A symmetric bracket sequence is defined as a non-empty string satisfying one of the following conditions.

• ()
• A string obtained by concatenating (, $s$, ) in this order, for some symmetric bracket sequence $s$

Also, for a string $s$ consisting of ( and ), its score is defined as follows.

• The number of times the following operation can be repeated.
• Among the contiguous subsequences of $s$ that are symmetric bracket sequences, choose $1$ longest one and delete it.
• It can be proved that this number is uniquely determined regardless of the order in which the subsequences are removed.

There is a string $S$ of length $N$ consisting of ( and ).

You are given $Q$ queries on $S$; process them in order. There are $2$ types of queries, whose input formats and contents are as follows.

• 1 i: Change the $i$-th character of $S$ to the one of (, ) that differs from the current character.
• 2 l r: Output the score of the substring obtained by taking the $l$-th through $r$-th characters of $S$.

Input

$N$ $Q$
$S$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

• $N$ is an integer satisfying $1 \leq N \leq 2 \times 10^5$
• $Q$ is an integer satisfying $1 \leq Q \leq 2 \times 10^5$
• $S$ is a string of length $N$ consisting of ( and )
• For queries of the form 1 i, $i$ is an integer satisfying $1 \leq i \leq N$
• For queries of the form 2 l r, $l, r$ are integers satisfying $1 \leq l \leq r \leq N$
• Queries of the form 2 l r appear at least $1$ time

Output

For each query of the form 2 l r, output the answer on $1$ line.

Print a newline after each output query $1$.

Sample

5 3
(()))
2 1 4
1 4
2 2 5

1
2