题目描述

你有 $N$ 个整数，$A_1, A_2, ..., A_N$。你需要处理两种操作。一种操作是在给定区间的每个数字上加上某个数。另一种是询问给定区间内数字的总和。

输入格式

第一行包含两个数字 $N$ 和 $Q$。$1 ≤ N,Q ≤ 10^5$。

第二行包含 $N$ 个数字，是 $A_1, A_2, ..., A_N$ 的初始值。$-10^9 ≤ A_i ≤ 10^9$。

接下来的 $Q$ 行，每行代表一个操作。

"C a b c" 表示将 $c$ 加到 $A_a, A_{a+1}, ..., A_b$ 的每个数字上。$-10000 ≤ c ≤ 10000$。

"Q a b" 表示查询 $A_a, A_{a+1}, ..., A_b$ 的总和。

输出格式

你需要按顺序回答所有查询操作。每行一个答案。

样例

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