Description

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.

Input

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.

Output

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

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
Hint
The sums may exceed the range of 32-bit integers.
代碼：
pushdown的時候要向下累加。
#include<iostream>#include<cstring>#include<cstdio>#include<cstdlib>#include<ctype.h>    //tower()#include<set>  #include<map>  #include<iomanip>// cout<<setprecision(1)<<fixed<<a;#include<vector>   #include<cmath>	#include<algorithm>#include<bitset>#include<limits.h>#include<stack>#include<queue>using namespace std;const __int64 maxn=100010;const __int64 inf=0x7fffffff;#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1__int64 add[maxn<<2];//維護當(dāng)前l(fā)azy值 __int64 sum[maxn<<2];//線段樹維護當(dāng)前區(qū)間和 void pushup(__int64 rt){//當(dāng)前結(jié)點信息更新到父結(jié)點	sum[rt]=sum[rt<<1]+sum[rt<<1|1]; }void pushdown(__int64 rt,__int64 num){	if(add[rt]){		add[rt<<1]+=add[rt];				//+=  not  =		add[rt<<1|1]+=add[rt];		sum[rt<<1]+=add[rt]*(num-(num>>1));		sum[rt<<1|1]+=add[rt]*(num>>1);		add[rt]=0;	}}void build(__int64 l,__int64 r,__int64 rt){	add[rt]=0;	if(l==r){		scanf("%I64d",&sum[rt]);		return;	}	__int64 mid=(l+r)>>1;	build(lson);	build(rson);	pushup(rt);}void update(__int64 a,__int64 b,__int64 c,__int64 l,__int64 r,__int64 rt){	if(a<=l&&b>=r){		add[rt]+=c;				//+=  not  =		sum[rt]+=c*(r-l+1);		return;	}	pushdown(rt,r-l+1);	__int64 mid=(l+r)>>1;	if(a<=mid) update(a,b,c,lson);	if(b>mid) update(a,b,c,rson);	pushup(rt);}__int64 query(__int64 a,__int64 b,__int64 l,__int64 r,__int64 rt){	if(a<=l&&b>=r) return sum[rt];	pushdown(rt,r-l+1);	__int64 mid=(l+r)>>1;	__int64 s=0;	if(a<=mid) s+=query(a,b,lson);	if(b>mid) s+=query(a,b,rson);	return s;}int main(){//G++:5888K	2985MS    C++:5360K	2000MS    __int64 n,m,a,b,c;    char s[2];    while(scanf("%I64d%I64d",&n,&m)==2){    	memset(sum,0,sizeof(sum));        build(1,n,1);        while(m--){            scanf("%s",s);            if(s[0]=='Q'){//查詢                scanf("%I64d%I64d",&a,&b);                printf("%I64d/n",query(a,b,1,n,1));            }            else{//染色                 scanf("%I64d%I64d%I64d",&a,&b,&c);                update(a,b,c,1,n,1);            }        }    }    return 0;}