Description

给出了一个序列，你需要处理如下两种询问。

"C a b c"表示给[a, b]区间中的值全部增加c (-10000 ≤ c ≤ 10000)。

"Q a b" 询问[a, b]区间中所有值的和。

Input

第一行包含两个整数N, Q。1 ≤ N,Q ≤ 100000.

第二行包含n个整数，表示初始的序列A (-1000000000 ≤ Ai ≤ 1000000000)。

接下来Q行询问，格式如题目描述。

Output

对于每一个Q开头的询问，你需要输出相应的答案，每个答案一行。

Sample Input

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

Sample Output

455915 这个题搞了不少时间，主要是难懂，而且写代码稍微快一点就 各种错误，吓得我不敢写快了，以后还是要多多细心才行。 这道题用开始那种线段树已经不行了，必须想出效率更高的方法，于是延迟标记出来了，用sign数组表示，它主要用于记录目前更新或者查询到的节点，并且它很懒，不更新未到节点，直到某次查询或者更新到标记的节点的子节点时 这个时候就把当前节点更新了，去掉节点标记时需要把子节点标记。 此次代码重点：区间更新，延迟标记

#include
      
       #include
       
        #include
        
          #include
         
           #include
          
            using namespace std; #define INF 0x3f3f3f3f #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int MX = 100050; long long sum[MX<<2]; long long sign[MX<<2]; int T, n, Q, X, Y; long long Z; void PushUp(int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } void PushDown(int rt, int len) { if (sign[rt]) { sign[rt<<1] += sign[rt]; sign[rt<<1|1] += sign[rt]; sum[rt<<1] += (len - (len>>1)) * sign[rt];//为了解决奇数所带来的子节点分配不平衡问题，因此需要这样做 sum[rt<<1|1] += (len>>1) * sign[rt]; sign[rt] = 0; } } void Build(int l, int r, int rt) { sign[rt] = 0;//初始化标记 if (l == r) { scanf("%lld", &sum[rt]); return ; } int m = (l + r)>>1; Build(lson); Build(rson); PushUp(rt); } void Update(int L, int R, long long z, int l, int r, int rt) { if (L <= l && r <= R) { sign[rt] += z;//记录下更新的值 sum[rt] += z * (r - l + 1);//批量更新 return ; } PushDown(rt, r - l + 1);//检查标记，看是否需要继续向下更新 int m = (l + r)>>1