题目描述

给出一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$。现在要支持 $m$ 次操作，操作有两种：

• 1 x y k：把 $a_x,a_{x+1},\dots,a_y$ 中的每个数都加上 $k$；
• 2 x y：输出 $\sum\limits_{i=x}^{y}a_i$。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

接下来 $m$ 行，每行第一个整数为 $1$ 或 $2$ 表示操作类型，含义如上。

输出格式

对每个 2 操作输出一行一个整数，表示区间和。

输入输出样例 #1

输入 #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

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 2\times 10^5$，$1\le m\le 2\times 10^5$，$|a_i|\le 10^6$，$|k|\le 10^6$，操作中出现的 $x,y$ 均满足 $1\le x\le y\le n$。题目保证任何时刻序列中每个数的绝对值都不超过 $6\times 10^9$，但区间和会更大，请使用 $64$ 位整数。