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 <iostream>

#include <cstdio>

using namespace std;

typedef long long ll;

const int MAXN=;

struct Node{

    ll sum,lazy;

    int l,r;

};

struct SegmentTree{

private:

    Node a[MAXN*];

public:

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

    {

        a[rt].l=l;

        a[rt].r=r;

        a[rt].lazy=;

        if(l==r)

        {

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

            return ;

        }

        int mid=(a[rt].l+a[rt].r)>>;

        build(rt<<,l,mid);

        build(rt*+,mid+,r);

        a[rt].sum=a[rt<<].sum+a[rt*+].sum;

    }

    void pushDown(int rt)

    {

        int mid=(a[rt].l+a[rt].r)>>;

        a[rt<<].sum+=(mid-a[rt].l+)*a[rt].lazy;

        a[rt*+].sum+=(a[rt].r-mid)*a[rt].lazy;

        a[rt<<].lazy+=a[rt].lazy;

        a[rt*+].lazy+=a[rt].lazy;

        a[rt].lazy=;

    }

    void change(int rt,int l,int r,int val)

    {

        if(a[rt].l==l&&a[rt].r==r)

        {

            a[rt].sum+=(r-l+)*val;

            a[rt].lazy+=val;

            return ;

        }

        if(a[rt].lazy!=)

        {

            pushDown(rt);

        }

        int mid=(a[rt].l+a[rt].r)>>;

        if(r<=mid)

        {

            change(rt<<,l,r,val);

        }

        else if(mid<l)

        {

            change(rt*+,l,r,val);

        }

        else

        {

            change(rt<<,l,mid,val);

            change(rt*+,mid+,r,val);

        }

        a[rt].sum=a[rt<<].sum+a[rt*+].sum;

    }

    ll query(int rt,int l,int r)

    {

        if(a[rt].l==l&&a[rt].r==r)

        {

            return a[rt].sum;

        }

        if(a[rt].lazy!=)

        {

            pushDown(rt);

        }

        int mid=(a[rt].l+a[rt].r)>>;

        if(r<=mid)

            return query(rt<<,l,r);

        else if(mid<l)

            return query(rt*+,l,r);

        else

        {

            return query(rt<<,l,mid)+query(rt*+,mid+,r);

        }

    }

};

SegmentTree solver;

int n,m;

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        solver.build(,,n);

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

        {

            scanf("%*c");

            char op;

            scanf("%c",&op);

            if(op=='Q')

            {

                int l,r;

                scanf("%d%d",&l,&r);

                printf("%lld\n",solver.query(,l,r));

            }

            else

            {

                int l,r,val;

                scanf("%d%d%d",&l,&r,&val);

                solver.change(,l,r,val);

            }

        }

    }

    return ;

}