Description

对每个测试用例，都输出一行“$Case$#$t$:”（不带引号，$t$表示测试用例的编号），对每种操作都输出已更新单元格的颜色值。《到月球去》是RPG公司开发的一款角色扮演冒险游戏，登月的前提是有一种技术能让我们永久重建临终人类的记忆。假设有$n$个整数$A[1],A[2],…,A[n]$，实现以下操作：

①$C$ $l$ $r$ $d$：每个$A$ $i$$（l≤i≤r）$都增加一个常数$d$，并将时间戳增加$1$，这是唯一导致时间戳增加的操作；

②$Q$ $l$ $r$：查询$A$ $i$$（l≤i≤r）$的当前和；

③$H$ $l$ $r$ $t$：查询$t$时间$A$ $i$$（l≤i≤r）$的历史和；

④$B$ $t$：回到时间$t$。一旦决定回到过去，就再也不可以访问一个前进版了。

其中，$n、m≤10^5$，$|A[i]|≤10^9$，$1≤l≤r≤n$，$|d|≤10^4$。系统从时间$0$开始，第$1$次修改是在时间$1$，$t≥0$，不会向我们介绍未来的状态。

Format

Input

输入包含多个测试用例，每个测试用例的第1行都包含两个整数n和m，表示元素个数和操作数；第$2$行包含$n$个整数$A[1],A[2],…,A[n]$；接下来有m行，每行都表示一种操作。

Output

对每个查询，都单行输出结果。

Samples

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

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

4
55
9
15

0
1