#4603. 「2021 营员交流」大毒瘤

「2021 营员交流」大毒瘤

Description

有一排 nn 坑位。这些坑位都可以种树。

有时候,小 ω\omega 会在一个区间释放一个魔法,使得这个区间的树高度增加 kk (高度为 00 的也会生长)。

有时候,小 ω\omega 会询问一个区间的树的高度之和。

有时候,会产生一场大火,每次操作之后,火都会蔓延到左右两个格子,火经过的格子,树的高度都会变成 00

有时候,小 ω\omega 会把一个区间的火给浇灭。

具体的来说,每次小 ω\omega 会释放一个魔法/进行一个询问/放一把火/浇灭一个区间的火。然后,每个火会燃烧到左边,右边,和自己原来的位置。

如果一个位置有多个火,和一个效果相同,然后所有有火的位置的树高度都变为了 0,即使施加了法术,这个位置的树高度依然为 0。

ω\omega 发现他借来的 Debian\mathrm{Debian} 机坏了,只能来求助于你。

Input

第一行俩正整数 n,qn, q

下面一行 nn 个整数表示初始状态下每个位置的树的高度。

下面 qq 行,每行第一个正整数 opi\mathrm{op}_i

opi=1\mathrm{op}_i=1 ,那么下面紧跟仨正整数 li,ri,kil_i,r_i,k_i,表示对区间 [li,ri][l_i,r_i] 释放了一次魔法,让树的高度增加了 kik_i

opi=2\mathrm{op}_i=2 ,那么下面紧跟俩正整数 li,ril_i,r_i,表示进行了一次询问。

opi=3\mathrm{op}_i=3,那么下面紧跟一个正整数 posi\mathrm{pos}_i,表示 posi\mathrm{pos}_i 发生了一场大火。

opi=4\mathrm{op}_i=4,那么下面紧跟俩正整数 li,ril_i,r_i,表示浇灭了 lil_irir_i 的大火。

Output

若干行每行一个整数,表示每个询问的答案。

Samples

8 15
4 5 6 7 1 5 8 1
4 7 7
4 1 8
2 4 4
2 3 6
2 3 7
2 2 5
2 3 7
2 4 8
1 2 4 3
4 4 4
1 1 5 6
2 6 7
2 3 3
2 5 8
2 3 4

7
19
27
19
27
22
13
15
21
31

Limitation

对于所有的数据,$1 \leq l_i\leq r_i \leq n \leq 10^5,1 \leq q \leq 5 \times 10^5,1 \leq a_i,k_i \leq 10^5$。

子任务 分值 nn qq 特殊性质 依赖的子任务
1 1919 n1000n \leq 1000 q1000q \leq 1000
2 2626 n100000n \leq 100000 q100000q \leq 100000 保证数据随机
3 88 opi4\mathrm{op}_i\neq 4
4 1717 n50000n \leq 50000 q50000q \leq 50000 11
5 3030 n100000n \leq 100000 q500000q \leq 500000 1,2,3,41,2,3,4

友情提醒:请相信自己算法的常数。