VS String Queries

We are given a binary string (a) of length (n) (indexed from 1 to (n)). A string (x) of length (\ge 2) is called a "VS string" if every contiguous substring of length 2 has an XOR value equal to (1), i.e. every two consecutive characters are different. In other words, a VS string is an alternating binary string such as (01), (10), (010), (101), etc.

You need to maintain the binary string (a) and process (q) operations. The operations are of the following five types:

[ \def\arraystretch{1.5} \begin{array}{|c|c|} \hline \textbf{Format} & \textbf{Description} \ \hline \mathtt{0\ l\ r} & Set all bits in the interval ([l, r]) to (0). \ \hline \mathtt{1\ l\ r} & Set all bits in the interval ([l, r]) to (1). \ \hline \mathtt{2\ l\ r} & Flip every bit in the interval ([l, r]) (i.e. change (0) to (1) and (1) to (0)). \ \hline \mathtt{3\ l\ r\ k} & Query: count how many contiguous substrings of length (k) within ([l, r]) are VS strings. (Note that by definition, VS strings have length at least (2).) \ \hline \mathtt{4\ l\ r} & Query: output the length of the longest contiguous VS substring within ([l, r]). If no substring of length (\ge 2) exists, output (1). \ \hline \end{array} ]

The input begins with two integers (n) and (q). The next line contains the binary string (a) (without spaces). Then (q) lines follow, each representing one operation.

Your task is to process all operations. For the query operations (types (3) and (4)), print the answer on a separate line.

inputFormat

The first line contains two integers (n) and (q) ( (\text{length of the string and number of operations}) ). The second line is a binary string of length (n). Each of the following (q) lines contains an operation in one of the following formats:

• 0 l r : Set all bits in ([l, r]) to (0). • 1 l r : Set all bits in ([l, r]) to (1). • 2 l r : Flip all bits in ([l, r]). • 3 l r k : Query and output the number of substrings of length (k) in ([l, r]) that are VS strings. • 4 l r : Query and output the maximum length of a VS substring in ([l, r]). If none exists (i.e. no substring of length (\ge 2) is alternating), output (1).

outputFormat

For each query operation (types (3) and (4)), output the result on a separate line.

sample

6 7
101010
3 1 6 2
4 1 6
2 2 5
3 1 6 2
4 1 6
0 3 3
4 3 3

5
6
3
4
1