背景故事

第三讲师郑老板在模拟一颗线段树，但粗心的他总是不小心将数据输错。
为了避免浪费时间，他决定使用时间回档，回到过去来修改错误。
但粗心的他又可能会在时间回档时出错。
现在头脑混乱的他已经完成不了线段树了，所以向你请求帮助。

问题描述

郑老板给出n个整数 $a_1, a_2, …, a_n$ 。对于这些整数，郑老板进行了以下操作，需要你来帮助他实现：
1. C l r d: 对于从$l$到$r$的每一个元素，添加一个常数$d$，并将时间$+1$，注意：这是唯一的会导致时间增加的操作。
2. Q l r: 询问当前从$l$到$r$的元素的值的总和。
3. B t: 返回时间$t$的状态。但是一旦你回到时间$t$，你就不能返回$t$之后的时间。
数据范围：$n,m \leq 10^5$, $|a_i| \leq 10^4$, $1 \leq l \leq r \leq N$ , $|d| \leq 10^4$ 。
系统是从时间$0$开始的，第一次修改是在时间$1$，$t \geq 0$，如果$t$是在未来，则时间回档失败，不改变时间。

输入格式

第一行有两个整数$n,m$分别表示总点数和总时间。
第二行有$n$个整数分别为$a_1 a_2 … a_n$
接下来$m$行是$m$个操作。

输出格式

对于每一个询问，输出对应的结果。

部分分

对于30%的数据，$n,m \leq 100$
对于50%的数据，$n,m \leq 1000$
对于70%的数据，$n,m \leq 10000$
对于100%的数据，$n,m \leq 100000$

Sample 1

Input

10 7
1 2 3 4 5 6 7 8 9 10
Q 2 7
C 3 8 3
Q 2 7
C 5 10 1
Q 2 7
B 1
Q 2 4

Output

27
42
45
15

时空限制

1s
256MB