题目描述

这是一道模板题。

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：

1. 区间加一个数；
2. 查询区间的历史和；

历史和定义为数列 $h_i$ 的区间和：初始 $h_i=a_i$，在每次操作（修改或查询，具体可参考样例解释）完成后，对所有 $h_i \leftarrow h_i+a_i$。

输入格式

第一行两个数 $n, m$，表示长度为 $n$ 的有序序列和 $m$ 个操作。
第二行有 $n$ 个数，表示有序序列 $a_i$。

下面有 $m$ 行，每行第一个数表示操作类型：

1. 之后有三个数 $l, r, x$ 表示将在区间 $[l,r]$ 之间的值都加上 $x$；
2. 之后有两个数 $l, r$ 表示查询区间 $[l, r]$ 的历史和。

输出格式

对于每个操作 $2$ 各输出一行，表示查询结果。

5 6
5 2 13 12 9
2 3 5
1 1 3 17
2 1 2
2 1 4
2 4 5
1 4 5 9

34
55
230
105

10 10
8 9 2 6 2 8 8 3 10 6
1 7 9 8
2 2 6
2 1 8
2 8 10
1 3 8 10
2 5 8
2 8 9
1 8 9 1
2 5 10
2 5 6

54
170
124
246
207
687
200

数据范围与提示

对于 $15\%$ 的数据，$n,m \leq 20$；
对于 $50\%$ 的数据，$n,m \leq 3000$；
对于 $100\%$ 的数据，$1 \leq n,m \leq 10^5, -1000 \leq a_i,x \leq 1000$。