题目描述

维护一个长度为 $n$ 的整数序列 $a$，支持三种操作：

• 1 u v c，对于 $\forall i \in [u,v]$，将 $a_i$ 更改为 $c$；
• 2 u v c，对于 $\forall i \in [u,v]$，将 $a_i$ 更改为 $\max(a_i+c,0)$；
• 3 u v，输出 $\sum \limits_{i=u}^v [a_i=0]$ 的值。

输入格式

第一行输入两个正整数 $n,m$，表示序列长度和操作个数。

第二行输入 $n$ 个整数 $a_i$，表示序列的初始状态。

第三行开始，往下 $m$ 行，每行表示一个操作。

输出格式

输出若干行，每行一个整数，依次回答每个操作 $3$ 的问题。

5 3
6 4 6 6 4 
2 1 5 -5
1 3 4 4
3 1 5

2

提示

对于 $100\%$ 的数据，$1\leq n,m\leq 3\times 10^5$，$0\leq a_i\leq 10^9$。

• 对于操作 $1$，保证 $0\leq c\leq 10^9$。
• 对于操作 $2$，保证 $|c| \leq 10^9$。

且对于所有操作，保证 $1\leq u\leq v\leq n$。