193 线段树历史和

这是一道模板题。

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

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

初始 $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}$。

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