<? echo $row['title']." - ".$MSG_PROBLEM."

Description

你有N个整数，A1，A2，An。你需要处理两种操作。一种操作是在给定的区间内将某个给定的数字添加到每个数字上。另一种是求给定区间内的数字之和。

You have N integers, A₁, A₂, ... , 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

第一行包含两个数字N和Q.1≤N，Q≤100000。
第二行包含N个数字，A1、A2、…的初始值.-1000000000≤Ai≤1000000000。
接下来的Q行中的每一行表示一个操作。
“C a b c”是指将c加到Aa、Aa+1、…Ab中的每一个数字上，-10000≤c≤10000。
“Q a b”表示查询Aa，Aa+1，…Ab 的总和。

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A₁, A₂, ... , 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₊₁, ... , A_b. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of A_a, A_a₊₁, ... , A_b.

Output

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

Sample Input Copy

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 Copy

Source/Category