[SCOI2010]序列操作

题目描述

lxhgww 最近收到了一个 $01$ 序列,序列里面包含了 $n$ 个数,下标从 $0$ 开始。这些数要么是 $0$,要么是 $1$,现在对于这个序列有五种变换操作和询问操作: - `0 l r` 把 $[l, r]$ 区间内的所有数全变成 $0$ - `1 l r` 把 $[l, r]$ 区间内的所有数全变成 $1$ - `2 l r` 把 $[l,r]$ 区间内的所有数全部取反,也就是说把所有的 $0$ 变成 $1$,把所有的 $1$ 变成 $0$ - `3 l r` 询问 $[l, r]$ 区间内总共有多少个 $1$ - `4 l r` 询问 $[l, r]$ 区间内最多有多少个连续的 $1$ 对于每一种询问操作,lxhgww 都需要给出回答,聪明的程序员们,你们能帮助他吗?

输入输出格式

输入格式


第一行两个正整数 $n,m$,表示序列长度与操作个数。 第二行包括 $n$ 个数,表示序列的初始状态。 接下来 $m$ 行,每行三个整数,表示一次操作。

输出格式


对于每一个询问操作,输出一行一个数,表示其对应的答案。

输入输出样例

输入样例 #1

10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9

输出样例 #1

5
2
6
5

说明

【数据范围】 对于 $30\%$ 的数据,$1\le n,m \le 1000$; 对于$100\%$ 的数据,$1\le n,m \le 10^5$。