Description

给定由 N 个整数构成的数列，再给定 M 条指令，每条指令可能是如下两种之一：

1. C l r d，表示将区间 [l,r] 之间的每个数都加上整数 d ；

2. Q l r，表示询问区间 [l,r] 之间所有数的和；

对于每次询问，请输出对应的和。

Input Format

第 1 行有 2 个整数 N 和 M 。

第 2 行有 N个整数，空格隔开。

接下来 M 行，每行读入一条题目描述的指令。

数据范围

1≤N,M≤105，1≤l,r≤N， −10000≤d≤10000，读入的 N 个整数的值在 [−109,109] 范围。

Output Format

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

Source