题目描述

给定由 $N$ 个整数构成的数列，再给定 $M$ 条指令，每条指令可能是如下两种之一：

1. $C$ $l$ $r$ $d$ ，表示将区间 $[l,r]$ 之间的每个数都加上整数 $d$ ；
2. $Q$ $l$ $r$ ，表示询问区间 $[l,r]$ 之间所有数的和；

对于每次询问，请输出对应的和。

输入

第 $1$ 行有 $2$ 个整数 $N$ 和 $M$ 。

第 $2$ 行有 $N$ 个整数，空格隔开。

接下来 $M$ 行，每行读入一条题目描述的指令。

数据范围

$1≤N,M≤10^5$ ， $1 \le l,r \le N$ ，

$-10000≤d≤10000$ ，读入的 $N$ 个整数的值在 $[-10^9,10^9]$ 范围。

输出

输出若干行，每行一个整数，代表了对于每次询问输出的结果。

样例

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