题目描述

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

输入

第一行包含两个数字 N 和 Q.$1，≤ N，Q ≤ 100000$。

第二行包含 N 个数字，初始值为 $A1、A2、...、AN$。 $-1000000000 ≤ Ai ≤ 1000000000$。

接下来的每一条 Q 行都表示一个操作。

“C a b c”表示将 c 添加到 Aa， Aa+1， ...， Ab.$-10000 ≤ c ≤ 10000$中的每一个。

“Q a b”表示查询 Aa、Aa+1、...、Ab 的总和。

输出

您需要按顺序回答所有 Q 命令。一行一个答案。

样例

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

提示

总和可能超出 32 位整数的范围。