Description

给出 n 个整数a[1],a[2],...,a[n] .

q 次操作，共有两种操作：

$1$ $l$ $r$ 查询 ${\textstyle \sum_{i=l}^{r}}a[i]$.

$2$ $l$ $r$ $w$ $a[i]\longleftarrow a[i]+w$ $(l\le i\le r)$

Format

Input

第一行有两个正整数 $n$ $q$ ， $n$ 表示数组长度， $q$ 表示操作次数.

第二行有 $n$ 个整数 $a[1],a[2],...,a[n]$.

接下来 $q$ 行，每行第一个数是 $op$ 表示操作类型

若 $op=1$ 再输入 $l,r$ 表示查询 ${\textstyle \sum_{i=l}^{r}}a[i]$.

若 $op = 2$ 再输入 $l,r,w$ 表示令 $a[i]\longleftarrow a[i]+w$ $(l\le i\le r)$.

$op\in \left \{1, 2 \right \}$ $1\le n,a[i],q,w\le 10^{6}$ $1\le l\le r\le n$

Output

对于每次查询操作输出一个整数表示 ${\textstyle \sum_{i=l}^{r}}a[i]$.

Samples

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

12