You have N integers, A₁, A₂, ... , A_N. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of A_a, A_a+1, ... , A_b. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of A_a, A_a+1, ... , A_b.

You need to answer all Q commands in order. One answer in a line.

 #include<cstdio>

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define MAXN 100100

 #define LL long long

 LL sum[MAXN<<];

 LL add[MAXN<<];

 int n,q;

 char s[];

 void putup(int rt)

 {

     sum[rt] = sum[rt<<]+sum[rt<<|];

 }

 void putdown(int rt,int m)

 {

     if (add[rt])

     {

         add[rt<<] += add[rt];

         add[rt<<|] += add[rt];

         sum[rt<<] += (m-(m>>))*add[rt];

         sum[rt<<|] += (m>>)*add[rt];

         add[rt] = ;

     }

 }

 void build(int l,int r,int rt)

 {

     add[rt] = ;

     if (l==r)

     {

         scanf("%lld",&sum[rt]);

         return ;

     }

     int m = (l+r)>>;

     build(lson);

     build(rson);

     putup(rt);

 }

 void update(int l,int r,int rt,int L,int R,int c)

 {

     if (L<=l && r<=R)

     {

         add[rt] += c;

         sum[rt] += (LL)c*(r-l+);

         return ;

     }

     putdown(rt,r-l+);

     int m = (l+r)>>;

     if (L<=m) update(lson,L,R,c);

     if (R>m)  update(rson,L,R,c);

     putup(rt);

 }

 LL query(int l,int r,int rt,int L,int R)

 {

     if (L<=l && r<=R)

     {

         return sum[rt];

     }

     putdown(rt,r-l+);

     LL ret = ;

     int m = (l+r)>>;

     if (L<=m) ret += query(lson,L,R);

     if (R>m)  ret += query(rson,L,R);

     return ret;

 }

 int main()

 {

     scanf("%d%d",&n,&q);

     build(,n,);

     while (q--)

     {

         int x,y,z;

         scanf("%s",s);

         if (s[]=='C')

         {

             scanf("%d%d%d",&x,&y,&z);

             update(,n,,x,y,z);

         }

         else

         {

             scanf("%d%d",&x,&y);

             printf("%lld\n",query(,n,,x,y));

         }

     }

     return ;

 }