时间限制：1秒　　内存限制：256M

---

【题目描述】

　　现在给你一个整数序列：\(A[1],A[2],…,A[N]\)，你需要实现下列几种操作：

　　\(C\ l\ r\ d\)：把 \(A[l]..A[r]\) 每个元素加 \(d\)，并且时间计数器 timestamp 增加 1。

　　\(Q\ l\ r\)：查询当前序列中 \(A[l]+A[l+1]+...+A[R]\) 和。

　　\(H\ l\ r\ t\)：查询时刻 \(t\) 时的序列中 \(A[l]+A[l+1]+...+A[R]\) 和。

　　\(B\ t\)：回到时刻 \(t\) 时的序列状态。一旦你决定回到过去，你就永远无法再进入该时刻之后的版本了。

　　最开始，时间计数器timestamp=0，即时刻 0，第一次修改，则时间计数器变为 1。

【输入格式】

　　第一行 \(N,M\)，表示序列长度和操作数目。
　　第二行是序列 \(A[1]..A[N]\)。
　　再接下来的 \(M\) 行，每行一条操作命令，你应认为每条操作都是合法的。

【输出格式】

　　输出每次的查询结果。

【输入输出样例】

　Input

Input 1:
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

Input 2:
2 4
0 0
C 1 1 1
C 2 2 -1
Q 1 2
H 1 2 1

　Output

Output 1:
4
55
9
15

Output 1:
0
1

【数据限制】

　　对于 \(100\%\) 的数据，N, M ≤ 10^5, |A[i]| ≤ 10^9, 1 ≤ l ≤ r ≤ N, |d| ≤ 10^4$

【来源】

　　Mr.he