U529392 Annoying Sequences

请你维护一个长度为 $N$ 的序列 $a$（第一个元素下标从 $1$ 开始），要求支持如下 $4$ 种操作： 1. 给定区间 $[l,r]$, 求出 $\sum^{r}_{i=l} a_i$。 2. 给定区间 $[l,r]$，将序列 $a$ 区间内每个数加上 $x$。 3. 给定 $x$ 和 $y$，将 $a_x$ 改为 $max(a_x-k,0)$，并将 $a_y$ 加上 $k$。 4. 给定区间 $[l,r]$，将 $a_i \gets max(a_i-k,0)(l\le i\le r)$

第一行两个整数，$N$ 和 $q$，分别表示序列大小和操作的个数。 第二行有 $N$ 个整数，第 $i$ 个整数表示序列中的第 $i$ 个数 $a_i$。 接下来 $q$ 行，每行表示一个操作。每行首先给出操作类型的编号 $op$。 - 若 $op=1$，则接下来有两个正整数 $l,r$，表示上述操作 $1$。 - 若 $op=2$，则接下来有三个整数 $l,r,k$，表示上述操作 $2$。 - 若 $op=3$，则接下来有三个整数 $x,y,k$，表示上述操作 $3$。 - 若 $op=4$，则接下来有三个整数 $l,r,k$，表示上述操作 $4$。

对于每个 $op=1$ 的操作，输出一行一个整数表示答案。

### 样例解释#1 操作过程中 $a$ 序列元素变化如下： *[2,4,5,1,6,3,2,3]* *[6,8,9,5,6,3,2,3]* *[6,8,6,5,6,3,2,6]* *[6,2,0,0,0,3,2,6]* *[6,2,0,2,2,5,4,8]* *[3,0,0,0,0,2,1,8]* ### 数据范围 #### 【数据范围】 - 对于 $10\%$ 的数据保证 $1\le n,q\le 10000$，$0\le a_i,k\le 1000$。 - 对于 $70\%$ 的数据保证 $1\le n,q\le 10^5$，且随机生成。 - 对于另外 $10\%$ 的数据保证无操作 $4$。 - 对于 $100\%$的数据保证 $1\le n,q\le 2\times 10^5$，$0\le a_i,k\le10^9$。