题目描述

给定一个长度为 $\red N$ 的数列 $\red A$，以及 $\red M$ 条指令，每条指令可能是以下两种之一：

$\red 1$、“C l r d”，表示把 $\red{A[l]}$ , $\red{A[l+1]}$ , $\red {......}$ , $\red{A[r]}$ 都加上 $\red d$。

$\red 2$、“Q l r”，表示询问数列中第 $\red{l\sim r}$ 个数的和。

对于每个询问，输出一个整数表示答案。

输入格式

第一行两个整数 $\red N$ , $\red M$。

第二行 $\red N$ 个整数 $\red{A[i]}$。

接下来 $\red M$ 行表示 $\red M$ 条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

样例

输入样例

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

输出样例

4
55
9
15

提示

$\red{1\le N,M\le 10^5}$,

$\red{|d|\le 10000}$,

$\red{|A[i]|\le 1000000000}$