Description

A valid parenthesis sequence is defined as follows:

1. The empty string is valid.
2. If string S is valid, then (S) is also valid.
3. If strings A and B are valid, then AB is also valid.

You are given a string of length $n$ consisting of ( and ), with positions numbered from $1$ to $n$. The following four operations are supported on this string:

• Replace a b c: change all parentheses in $[a, b]$ to $c$. For example, given the original string ))())())(, after performing Replace 2 7 (, it becomes )(((((()(.

• Swap a b: reverse the substring in $[a, b]$. For example, given the original string ))())())(, after performing Swap 3 5, it becomes ))))(())(.

• Invert a b: flip ( to ) and ) to ( within $[a, b]$. For example, given the original string ))())())(, after performing Invert 4 8, it becomes ))((()(((.

• Query a b: ask for the minimum number of positions in $[a, b]$ that must be changed to make the substring a valid parenthesis sequence. Changing a position means turning ( into ) or ) into (. Note that Query does not modify the current sequence. For example, given the original string ))())())(, the result of Query 3 6 is $2$, because you need to change position $5$ from ) to ( and position $6$ from ( to ).

Input Format

The first line contains two space-separated positive integers $n, q$, denoting the length of the string and the number of operations, respectively.
The second line contains the initial string $S$ of length $n$. The next $q$ lines each describe one operation to be performed in order. The operation name and its parameters are separated by single spaces.

Output Format

For each Query operation, output a single line with one integer representing the answer. The input is guaranteed to be solvable.

4 5
((((
Replace 1 2 )
Query 1 2
Swap 2 3
Invert 3 4
Query 1 4

1
2

Hint

Sample Explanation:

There are $2$ Query operations in the input, so the output has $2$ lines.
When executing the first Query, the parenthesis sequence is ))((. By changing position $1$, the substring over $[1, 2]$ becomes a valid parenthesis sequence, so the first output line is 1.

When executing the second Query, the parenthesis sequence is )((). You need to change position $1$ and position $2$ to make the substring over $[1, 4]$ a valid parenthesis sequence, so the second output line is 2.

Constraints:

For $30\%$ of the points, $1 \le n, q \le 3000$.
For $100\%$ of the points, $1 \le n, q \le 10^5$.

Translated by ChatGPT 5