Description

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

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

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

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

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

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

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

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

Input

第一行俩正整数 $n, q$。

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

下面 $q$ 行，每行第一个正整数 $\mathrm{op}_i$。

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

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

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

若 $\mathrm{op}_i=4$，那么下面紧跟俩正整数 $l_i,r_i$，表示浇灭了 $l_i$ 到 $r_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$。

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