Bracket String Transformation and Query

You are given a bracket string S of length \(n\) consisting of only round brackets and square brackets. In this problem, a string \(S\) is defined to be valid if and only if one of the following conditions holds:

• \(S\) is the empty string;
• \(S = [T]\) for some valid string \(T\);
• \(S = (T)\) for some valid string \(T\);
• \(S = TU\) where both \(T\) and \(U\) are valid strings.

For example, () and [()] are valid while [()]()) is not.

An operation is defined as follows: choose an interval \([l, r]\) and change every character in that interval by swapping its bracket type. That is, every round bracket becomes a square bracket and every square bracket becomes a round bracket. (Note that the bracket direction is preserved: an opening bracket remains opening, and a closing bracket remains closing.)

For a bracket string \(S\), define its weight \(val(S)\) as follows: if it is possible to transform \(S\) into a valid bracket string via a sequence of operations (possibly zero), then \(val(S)\) is the minimum number of operations required; otherwise, \(val(S)=0\).

You are given \(q\) queries. Each query is one of two types:

1. Modification query: given an interval \([l, r]\), perform the operation on that interval (i.e. flip every bracket in \(S[l, r]\)).
2. Query: given an interval \([l, r]\), calculate \[ \sum_{l' , r' \, \subseteq \, [l,r]} val(S[l',r']), \] where the sum is taken over every contiguous subinterval \([l',r']\) contained in \([l,r]\). (Note that indices are 1-indexed.)

Important details:

• The only characters in \(S\) are (', ')', '[' and ']'.
• The operation simply swaps round and square brackets without changing whether a bracket is opening or closing.
• A valid transformation is only possible if the underlying structure (i.e. the positions of openings and closings) is that of a valid bracket sequence. In other words, even after any number of operations, if the open/close pattern is not balanced the string cannot be valid.
• The weight \(val(S)\) is defined to be the minimum number of operations (each of which flips a contiguous segment) needed to convert \(S\) into a valid bracket string, or 0 if no sequence of operations can do so.

Hint on solving the problem:

You can observe that the operation toggles the type of bracket (round vs square) and that converting \(S\) into a valid string means ensuring that for every matching pair (determined by the intrinsic open/close structure) the two brackets have the same type. For a pair where the two brackets already have the same type, no operation is needed. For a pair with different types, you have a binary choice: you can flip either the opening or the closing bracket. When using range operations, if two forced flips occur on consecutive positions, they can be merged into one operation. Thus the problem reduces to, for each contiguous substring which is structurally valid, choosing for each mismatched pair one bracket to flip so as to minimize the number of contiguous flip segments. Then, summing \(val(S[l', r'])\) over all subintervals \([l',r']\) asked in the query.

inputFormat

The first line contains two integers \(n\) and \(q\) --- the length of the bracket string and the number of queries.

The second line contains a string \(S\) of length \(n\) consisting only of the characters (', ')', '[' and ']'.

Then \(q\) lines follow, each describing a query. Each query is in one of the following two forms:

• 1 l r --- a modification query: flip every bracket in the interval \([l, r]\).
• 2 l r --- a query: output the value of \[ \sum_{l' , r' \, \subseteq \, [l,r]} val(S[l',r']). \]

All indices are 1-indexed.

outputFormat

For each query of type 2, print a single integer representing the computed sum.

sample

4 3
([)]
2 1 4
1 2 3
2 1 4

1
0

</p>