Description

给定一个长为n的序列，接下来m次操作，每次操作会对序列某段区间内所有数加上一个值，或是询问一段区间的和。

Format

Input

第一行有两个整数 n，m(0<n,m<10^5)。
第二行有n个整数Ai，其中 -1000000000 ≤ Ai ≤ 1000000000。
接下去的m行是操作指令：
“C l r c” 表示数列区间[l,r]中每个数加上c。 -10000 ≤ c ≤ 10000.
"Q l r" 表示询问区间[l,r]的区间和。

Output

输出若干行，每行对应一个Q询问的结果。

Sample 1

Input

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

Output

4
55
9
15

Limitation

1s, 128MiB for each test case.

【提示】 结果可能超出32位整数。

Source

poj3468