题目描述

lxhgww 最近收到了一个 01 序列，序列里面包含了 $n$ 个数，这些数要么是 $0$，要么是 $1$，现在对于这个序列有五种变换操作和询问操作：

$0$ $a$ $b$ 把 $[a, b]$ 区间内的所有数全变成 $0$

$1$ $a$ $b$ 把 $[a, b]$ 区间内的所有数全变成 $1$

$2$ $a$ $b$ 把 $[a,b]$ 区间内的所有数全部取反，也就是说把所有的 $0$ 变成 $1$，把所有的 $1$ 变成 $0$

$3$ $a$ $b$ 询问 $[a, b]$ 区间内总共有多少个 $1$

$4$ $a$ $b$ 询问 $[a, b]$ 区间内最多有多少个连续的 $1$

对于每一种询问操作，lxhgww 都需要给出回答，聪明的程序员们，你们能帮助他吗？

输入格式

输入数据第一行包括 $2$ 个数，$n$ 和 $m$ ，分别表示序列的长度和操作数目

第二行包括 $n$ 个数，表示序列的初始状态

接下来 $m$ 行，每行 $3$ 个数，$op$ , $a$ , $b$ ，（$0 \le op \le 4$，$0 \le a \le b \lt n$）表示对于区间 $[a, b]$ 执行标号为 $op$ 的操作

输出格式

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

样例

input

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

output

5
2
6
5

数据范围与提示

对于 $30\%$ 的数据，$1 \le n, m \le 1000$

对于 $100\%$ 的数据，$1 \le n, m \le 100000$