背景故事

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

问题描述

郑老板给出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