题目描述

如题，已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上$k$。
2. 求出某区间每一个数的和。

输入输出格式

输入格式

第一行包含两个整数$n, m$，分别表示该数列数字的个数和操作的总个数。

第二行包含$n$个用空格分隔的整数，其中第$i$个数字表示数列第$i$项的初始值。

接下来$m$行每行包含$3$或$4$个整数，表示一个操作，具体如下：

1. 1 x y k：将区间$[x, y]$内每个数加上$k$。
2. 2 x y：输出区间$[x, y]$内每个数的和。

   输出格式

   输出包含若干行整数，即为所有操作 2 的结果。

   输入输出样例

   输入样例 #1

   5 5
   1 5 4 2 3
   2 2 4
   1 2 3 2
   2 3 4
   1 1 5 1
   2 1 4

   输出样例 #1

   11
   8
   20

   说明/提示

   对于$30\%$的数据：$n \le 8$，$m \le 10$。
   对于$70\%$的数据：$n \le {10}^3$，$m \le {10}^4$。
   对于$100\%$的数据：$1 \le n, m \le {10}^5$。

保证任意时刻数列中任意元素的和在$[-2^{63}, 2^{63})$内。

【样例解释】