题目描述

给定一个长度为$N$的数列 $A$，以及 $M$条指令，每条指令可能是以下两种之一：

1. C l r d，表示把 $A[l],A[l+1],…,A[r]$都加上 $d$。
2. Q l r，表示询问数列中第 $l∼r$个数的和。

对于每个询问，输出一个整数表示答案。

输入格式

第一行两个整数$N,M$。

第二行 $N$个整数 $A[i]$。

接下来 $M$行表示$M$ 条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

样例

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

数据范围

$1≤N,M≤10^5, |d|≤10000, |A[i]|≤10^9$

来源

• POJ3468
• 算法竞赛进阶指南