You have N integers, A1, A2, ... , AN. 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 A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000. 
Each of the next Q lines represents an operation. 
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000. 
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.

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

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<cmath>

 #include<cstdio>

 #define N 100007

 #define ll long long

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

     while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 int n,q;

 char ch[];

 #define ls p<<1

 #define rs p<<1|1

 struct seg

 {

     ll sum[N<<],add[N<<];

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

     {

         if (l==r)

         {

             sum[p]=read();

             return;

         }

         int mid=(l+r)>>;

         build(ls,l,mid),build(rs,mid+,r);

         sum[p]=sum[ls]+sum[rs];

     }

     void push_down(int p,int l,int r)

     {

         if (!add[p]) return;

         ll ad=add[p],mid=(l+r)>>;add[p]=;

         sum[ls]+=1ll*(mid-l+)*ad;

         sum[rs]+=1ll*(r-mid)*ad;

         add[ls]+=ad,add[rs]+=ad;

     }

     ll query(int p,int l,int r,int x,int y)

     {

         if (l==x&&y==r) return sum[p];

         push_down(p,l,r);

         int mid=(l+r)>>;

         if (y<=mid) return query(ls,l,mid,x,y);

         else if (x>mid) return query(rs,mid+,r,x,y);

         else return query(ls,l,mid,x,mid)+query(rs,mid+,r,mid+,y);

     }

     void modify(int p,int l,int r,int x,int y,int z)

     {

         sum[p]+=1ll*(y-x+)*z;

         if (l==x&&y==r)

         {

             add[p]+=z;

             return;

         }

         int mid=(l+r)>>;

         if (y<=mid) modify(ls,l,mid,x,y,z);

         else if (x>mid) modify(rs,mid+,r,x,y,z);

         else modify(ls,l,mid,x,mid,z),modify(rs,mid+,r,mid+,y,z);

     }

 }seg;

 #undef ls

 #undef rs

 int main()

 {

     n=read(),q=read();

     seg.build(,,n);

     for (int i=;i<=q;i++)

     {

         scanf("%s",ch);

         if (ch[]=='Q')

         {

             int x=read(),y=read();

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

         }

         else

         {

             int x=read(),y=read(),z=read();

             seg.modify(,,n,x,y,z);

         }

     }

 }