## Description:

You have *N* integers, *A*_{1}, *A*_{2}, ... , *A*_{N}. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

## Input:

The first line contains two numbers *N* and *Q*. 1 ≤ *N*,*Q* ≤ 100000.

The second line contains *N* numbers, the initial values of *A*_{1}, *A*_{2}, ... , *A*_{N}. -1000000000 ≤ *A*_{i} ≤ 1000000000.

Each of the next *Q* lines represents an operation.

"C *a* *b* *c*" means adding *c* to each of *A*_{a}, *A*_{a}_{+1}, ... , *A*_{b}. -10000 ≤ *c* ≤ 10000.

"Q *a* *b*" means querying the sum of *A*_{a}, *A*_{a}_{+1}, ... , *A*_{b}.

## Output:

You need to answer all *Q* commands in order. One answer in a line.

## Sample 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

## Sample Output:

4
55
9
15

## Note:

The sums may exceed the range of 32-bit integers.