Qarentheziz Sequence

Ryan is interested in strings made only of ( and ). He especially loves balanced strings. Any balanced string can be built with these rules:

• () is balanced.
• The concatenation of two balanced strings is balanced.
• If $T$ is balanced, then (, followed by $T$, followed by ) in this order is balanced.

For example, ()() and (()()) are balanced. )(, )()((), and ( are not balanced.

Ryan defines the sadness of a string $T$ as the minimum number of operations needed to turn $T$ into a balanced string. The operations can be used in any order and any number of times:

• Add ) to the beginning of $T$.
• Add ( to the end of $T$.
• Swap two adjacent characters of $T$.

Ryan has a string $S$ of length $N$ consisting only of ( and ). There are $Q$ queries, and you must process them in order. There are two kinds of queries.

• 1 l r: For each character from the $l$-th to the $r$-th character of $S$ (inclusive), change ( to ) and ) to (.
• 2 l r: Output the sadness of the substring of $S$ from the $l$-th to the $r$-th character.

The first line contains two integers $N$ and $Q$ ($2 \le N \le 150\,000$, $1 \le Q \le 150\,000$), separated by a space. The second line contains the string $S$, which consists only of ( and ) and has length $N$. Each of the next $Q$ lines contains three integers $t_i$, $l_i$, and $r_i$ ($1 \le t_i \le 2$, $1 \le l_i \le r_i \le N$), separated by spaces. At least one query has $t_i = 2$.

For each query with $t_i = 2$, print the sadness of the substring from the $l_i$-th to the $r_i$-th character on its own line.