题目描述

小橙拿到了一个长度为 $n$ 的 $01$ 序列,下标从 $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$。

对于每一个询问操作,都需要给出回答。请你编写程序完成这项任务。

输入格式

第一行两个正整数 $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$。