Sequence operation

Source: HDU

Version: Phuoc Hung OJ Extended

Problem Statement

Maintain a binary sequence with five operations: assign 0, assign 1, flip, count ones, and query the longest consecutive run of ones.

Input

The first line contains $n,m$ and the next line contains $n$ bits. Each operation is op a b, with zero-based indices.

• 0: assign the range to 0.
• 1: assign the range to 1.
• 2: flip all bits.
• 3: print the number of ones.
• 4: print the longest consecutive run of ones.

Output

Print one line for every type 3 or type 4 operation.

Subtasks

• 20 points: $n,m\le50$.
• 30 points: $n,m\le5000$.
• 50 points: $n,m\le10^5$, $0\le a\le b<n$.

Examples

Input

5 6
0 1 1 0 1
3 0 4
4 0 4
2 1 3
3 0 4
1 0 2
4 0 4

Output

3
2
2
5

Explanation

Initially there are 3 ones and the longest run has length 2. Flipping $[1,3]$ gives 0 0 0 1 1, leaving 2 ones. Assigning $[0,2]$ to 1 makes the whole sequence ones, so the final answer is 5.