Bracket Sequence Operations

A valid parentheses sequence is defined as follows:

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

You are given a string of length n consisting only of characters '(' and ')', with positions numbered from 1 to n. Then m operations are performed on the string. There are four types of operations:

• Replace a b c: Replace every character in the interval [a, b] with character c (which is either '(' or ')'). For example, if the original string is "()))())(" then after executing Replace 2 7 ( it becomes ")((((()(".
• Swap a b: Reverse the substring from position a to b. For example, if the original string is ")()))())(" then executing Swap 3 5 changes it to ") )))(())(" (the substring is reversed).
• Invert a b: Invert every character in the interval [a, b] (i.e. change '(' to ')' and vice versa). For example, if the original string is ")()))())(" then after Invert 4 8 it becomes ")((()(((".
• Query a b: Query the minimum number of positions you must change in the substring defined by the interval [a, b] so that it becomes a valid parentheses sequence. Changing a position means flipping the character (from '(' to ')' or vice versa). Note that a Query does not modify the string. For example, if the original string is ")()))())(" then Query 3 6 returns 2 since one way is to change position 5 from ')' to '(' and position 6 from '(' to ')'.

Note: Since a valid parentheses sequence must have even length, you can assume that every query is on an interval of even length. If an interval of odd length is queried, output -1.

inputFormat

The first line contains two integers n and m, representing the length of the string and the number of operations.

The second line contains a string of length n consisting of characters '(' and ')'.

Each of the following m lines contains an operation in one of the following formats:

• Replace a b c
• Swap a b
• Invert a b
• Query a b

outputFormat

For each Query operation, output a single line containing the minimum number of character flips required to transform the queried substring into a valid parentheses sequence. (If the length of the queried substring is odd, output -1.)

sample

9 5

()))())(

Replace 2 7 (
Swap 3 5
Invert 4 8
Query 3 6
Query 1 9

1
3