题目描述

江桥正在分发糖果！

糖果共有 $n$ 种，第 $i$ 种糖果初始有 $a_i$ 颗。

接下来会有 $q$ 名小朋友过来，每名小朋友只会执行下列操作之一：

拿取。格式为 1 l r k，表示从当前糖果中拿取第 $l$ 种到第 $r$ 种糖果各 $k$ 颗，如果某种糖果不够 $k$ 颗，则全部拿走。

查询。格式为 2 l r，表示查询当前第 $l$ 种到第 $r$ 种糖果总共还剩下多少颗。

由于江桥得知你编程技艺高超，因此他特意请你来帮他回答每次查询操作的答案。

输入格式

第一行两个正整数 $n,q$，表示糖果种类数和小朋友的数量。

接下来一行 $n$ 个正整数 $a_i$，表示第 $i$ 种糖果的初始数量。

接下来 $q$ 行，每行首先读入一个操作数 $op$，如果 $op = 1$，则表示拿取操作，再继续输入三个正整数 $l,r,k$ 表示从当前糖果中拿取第 $l$ 种到第 $r$ 种糖果各 $k$ 颗，如果某种糖果不够 $k$ 颗，则全部拿走。如果 $op = 2$，则表示查询操作，再继续输入两个正整数 $l,r$，表示查询当前第 $l$ 种到第 $r$ 种糖果总共还剩下多少颗。

输出格式

对于每次查询操作，输出一行一个数字表示答案。

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

7
6
6

样例解释

无

数据规模与约定

下发文件

下发文件对应子任务 $3$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n,q \leq 5 \times 10^3,1 \leq a_i,k\leq 10^9,op \in \{1,2\}, 1 \leq l \leq r \leq n$。