Migrated from Lutece 205 A Simple Problem with Integers

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

You have $N$ integers, $A_1, A_2, \cdots , 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

There is only one testcase.

The first line contains two numbers $N$ and $Q$. $1\leq N,Q\leq 100000$.

The second line contains $N$ numbers, the initial values of $A_1, A_2,\cdots , A_N$. $-1000000000\leq A_i\leq 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}, \cdots , A_b$. $-10000\leq c\leq 10000$.
• Q a b means querying the sum of $A_a, A_{a+1},\cdots , A_b$.

Output

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

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

Note

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

The data used in this problem is unofficial data prepared by standy. So any mistake here does not imply mistake in the offcial judge data.

Resources

POJ Monthly--2007.11.25, Yang Yi