Description

给出了一个序列，你需要处理如下两种询问。 “C a b c”表示给[a, b]区间中的值全部增加c (-10000 ≤ c ≤ 10000)。 “Q a b” 询问[a, b]区间中所有值的和。

Input Format

第一行包含两个整数N, Q。1 ≤ N,Q ≤ 100000. 第二行包含n个整数，表示初始的序列A (-1000000000 ≤ Ai ≤ 1000000000)。 接下来Q行询问，格式如题目描述。

Output Format

对于每一个Q开头的询问，你需要输出相应的答案，每个答案一行。

Sample

Sample Input

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

4 
55 
9 
15

Hint

1 ≤ N,Q ≤ 100000. -1000000000 ≤ Ai ≤ 1000000000