Description

有$N$ 个整数$A_1, A_2, …, A_N$ ，需要对其进行两种操作，一种操作是对给定区间中的每个数都添加一个给定的数，另一种操作是查询给定区间中数的总和。

Input

第$1$行包含两个数$N$ 和$Q （1≤N ，Q ≤10^5 ）$；第$2$行包含$N$ 个数，为$A_1 , A_2 , …, A_N$ 的初始值$（-10^9 ≤A_i ≤10^9 ）$；接下来的$Q$ 行，每行都表示一种操作，$“C a b c ”$表示将$A_a , A_{a +1} ,…, A_b$中的每一个数都加$c（-10^4 ≤c ≤10^4 ）$，“$Q a b$ ”表示查询$A_a , A_{a +1} , …, A_b$的总和。

Output

对每个查询，都单行输出区间和的值。

Samples

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

来源

POJ3468