题目描述

解决了之前的两个问题后，小陶还是意犹未尽。助教看小陶这么好学，就给他又出了一道题，并且承诺，如果小陶做出这道题目，期末就不会让他挂科。

给出一个有 $n$ 个元素的序列 $a$，进行 $m$ 次操作，操作有两种类型：

• $1\ x\ y\ c$：给 $a_x,a_{x+1},a_{x+2},\cdots ,a_{y−1},a_y$ 都加上 $c$。
• $2\ x\ y$：求 $a_x+a_{x+1}+a_{x+2}+\cdots +a_y$ 的值。

输入格式

第一行两个整数 $n,m$ ($1\le n,m\le 200000$)。

第二行 $n$ 个数，表示元素大小。

接下来 $m$ 行，每行三个或四个数表示一个操作，格式如题面所示。

输出格式

对于每个操作 $2$ ，输出一行一个数表示答案。

样例输入输出

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

4
55
9
15

说明/提示

对于 $10 \%$ 的数据， $n \leq 10, m \leq 20$ ；

对于 $30 \%$ 的数据： $n \leq 4000, m \leq 5000$ ；

对于 $60 \%$ 的数据: $n \leq 20000, m \leq 30000$ ；

对于 $100 \%$ 的数据: $2 \leq n \leq 100000,1 \leq m \leq 200000,1 \leq x \leq y \leq n, 0 \leq c \leq 10^{9}$ 。