Problem Description

Maintain an integer sequence $a$ of length $n$, supporting three operations:

• 1 u v c: for $\forall i \in [u,v]$, change $a_i$ to $c$.
• 2 u v c: for $\forall i \in [u,v]$, change $a_i$ to $\max(a_i+c,0)$.
• 3 u v: output the value of $\sum \limits_{i=u}^v [a_i=0]$.

Input Format

The first line contains two positive integers $n,m$, representing the sequence length and the number of operations.

The second line contains $n$ integers $a_i$, representing the initial state of the sequence.

Starting from the third line, the next $m$ lines each describe one operation.

Output Format

Output several lines, one integer per line, answering each operation $3$ in order.

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

2

Hint

For $100\%$ of the testdata, $1\leq n,m\leq 3\times 10^5$, $0\leq a_i\leq 10^9$.

• For operation $1$, it is guaranteed that $0\leq c\leq 10^9$.
• For operation $2$, it is guaranteed that $|c| \leq 10^9$.

For all operations, it is guaranteed that $1\leq u\leq v\leq n$.

Translated by ChatGPT 5