You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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$ 行，每行三个整数，表示一次操作。

输出格式

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

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

5
2
6
5

提示

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