线段树历史和

题目描述

这是一道模板题。

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

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$ 各输出一行，表示查询结果。

样例 1

输入

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

说明

初始 $h$ 序列为 $\{5, 2, 13, 12, 9\}$。

操作 2 3 5 虽然是询问操作，但仍然会更新 $h_i \leftarrow h_i+a_i$，更新结果为：$\{10, 4, 26, 24, 18\}$。注意更新在回答询问之后，即询问仍然是更新前 $h$ 的区间和。

操作 1 1 3 17 之后，序列 $a$ 为 $\{22, 19, 30, 12, 9\}$，$h$ 更新后为 $\{32, 23, 56, 36, 27\}$。

操作 2 1 2 即求此时的 $h_1+h_2$，答案即为 $32+23=55$。回答完该询问后更新 $h$，更新结果为 $\{54, 42, 86, 48, 36\}$。

样例 2

输入

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$。