Description

HSAHRBNU的（流动杯）篮球赛开始了，HeRaNO所在的班水的不行，又双叒叕全输了，小组赛滚粗……
HeRaNO is angry。篮球赛还没结束，所以搞点破坏是有效的。
放学后，HeRaNO来到了篮球场，HSAHRBNU的篮球场很有特点，有\(n\)个篮球架排成一排（处在一个篮球场的篮球架当做摆在一行处理）。HeRaNO发动一个召唤术ADD可以使得位置为\([l,r]\)范围内的篮球架升高或降低一个高度。这时HSD桑来到了篮球场，原来他们班也小组赛滚粗了，也想搞点破坏……HSD桑是高级玩家，可以发动一种变换叫做Sequence Change，可以让\([l,r]\)内的篮球架升高或降低一个与位置有关的等差数列，我们简记这种变换为变换\(\varphi\)，对于\([l,r]\)内位置为\(i\)的篮球架，可以使其升高\(i\times d(d>0)\)或降低\(-i\times d(d<0)\)的高度。
于是这两个人就不停地搞破坏……在一旁的FZ酱暗中记录下了所有的操作过程。（作为学生会长的）FZ酱需要计算出一些关键时间点时\([l,r]\)内篮球架的总高度（好找这两个人索要赔偿~）。那么计算的任务就交给你了！FZ酱说，赔偿款的一半是给你的！（他们交不交就不管FZ酱的事了~）

Format

Input

输入的第一行包括两个正整数\(n\)，\(T\)，\(n\)表示HSAHRBNU篮球场有的篮球架数，\(T\)表示HeRaNO和HSD桑进行操作的次数；
第二行为\(n\)个整数，第\(i\)个整数表示第\(i\)个篮球架的初始高度；
第三行到第\(T+2\)行，表示一个操作，形如：
1、ADD l r c：这是HeRaNO的操作，将\([l,r]\)内的篮球架整体升高\(c(c>0)\)或降低\(-c(c<0)\)的高度；
2、PHI l r d：这是HSD桑的操作，将\([l,r]\)的篮球架序列进行变换\(\varphi\)操作；
3、QUE l r：这是FZ酱的操作，查询\([l,r]\)内篮球架的高度和。

Output

对于每个QUE（也就是FZ酱的操作），输出一行，表示FZ酱想要的答案。

Sample

Input

10 10
37865 399994 929607 581321 82977 375502 56436 749569 607364 862800
PHI 6 6 397081
PHI 1 1 -159111
QUE 4 10
ADD 7 8 -660841
ADD 2 6 332959
ADD 1 5 751802
QUE 1 8
QUE 1 10
ADD 5 9 847104
QUE 1 10

Output

5698455
9538769
11008933
15244453

Limitation

共\(10\)个测试点，只有当输出与标准输出完全一致时可以获得\(10\text{pts}\)。
对于每个测试点，时间限制2s，空间限制512MiB。
对于\(30\%\)的测试点，\(n\le 2\times 10^3\)，\(T\le 2\times 10^3\)；
对于另\(20\%\)的测试点，\(n\le 10^5\)，\(T\le 2\times 10^4\)，且没有HSD桑的操作；
对于\(100\%\)的测试点，\(n\le 10^6\)，\(T\le 5\times 10^4\)，\(1\le l\le r\le n\)，所有整数的绝对值均小于\(2\times 10^{18}\)。
我们都知道，高度不能为负数，可是HeRaNO和HSD桑都使用了魔（膜）法，所以什么都可能发生……请当做他们把篮球架干掉后还刨了个坑……
这里高度数值有点大？这是因为HeRaNO对精度的要求非常高，但是进行小数操作太麻烦，于是他把高度都变成了整数，于是就这样了……

Source

HeRaNO's Test#2 Day2T3
Problem by HeRaNO