//Man always remember love because of romance only!
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid ((l+r)>>1)
inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int n,m,a[200001];
namespace segtree_mn{
	int tr[800001],tag[800001][2],tp[800001];
    void pushup(int x){
    	tr[x]=tr[x<<1]+tr[x<<1|1];
    	tp[x]=tp[x<<1]+tp[x<<1|1];
    }
    void pushdown(int x){
	    if(tag[x][0]){
	        tr[x<<1]=-tr[x<<1];
		    tr[x<<1|1]=-tr[x<<1|1];
		    if(tp[x<<1]) tag[x<<1][0]^=1,tag[x<<1][1]=-tag[x<<1][1];
		    if(tp[x<<1|1]) tag[x<<1|1][0]^=1,tag[x<<1|1][1]=-tag[x<<1|1][1];
	    }
	    if(tag[x][1]){
	        tr[x<<1]+=tp[x<<1]*tag[x][1];
	  	    tr[x<<1|1]+=tp[x<<1|1]*tag[x][1];
	        if(tp[x<<1]) tag[x<<1][1]+=tag[x][1];
	        if(tp[x<<1|1]) tag[x<<1|1][1]+=tag[x][1];
	    }
	    tag[x][0]=tag[x][1]=0;
    }
  	void build(int x,int l,int r){
	    if(l==r){
			tr[x]=0;
		    tag[x][0]=tag[x][1]=0;
		    tp[x]=0;
		    return;
	    }
	    build(x<<1,l,mid);
		build(x<<1|1,mid+1,r);
	    pushup(x);
  	}
	int query(int x,int l,int r,int nl,int nr){
	    if(!tp[x]) return 0;
	    if(nl<=l&&r<=nr) return tr[x];
	    pushdown(x);
	    int res=0;
	    if(nl<=mid&&tp[x<<1]) res+=query(x<<1,l,mid,nl,nr);
	    if(nr>mid&&tp[x<<1|1]) res+=query(x<<1|1,mid+1,r,nl,nr);
	    pushup(x);
	    return res;
	}
	void update(int x,int l,int r,int nl,int nr,int k){
	    if(!tp[x]) return;
	    if(nl<=l&&r<=nr){
	        tr[x]=-tr[x]+tp[x]*k;
	        tag[x][1]=-tag[x][1]+k;
	        tag[x][0]^=1;
	        return ;
	    }
	    pushdown(x);
	    if(nl<=mid&&tp[x<<1]) update(x<<1,l,mid,nl,nr,k);
	    if(nr>mid&&tp[x<<1|1]) update(x<<1|1,mid+1,r,nl,nr,k);
	    pushup(x);
	}
	void update2(int x,int l,int r,int id,int k){
	    if(l==r){
	        tr[x]=k;
	        tp[x]=1;
	        return;
	    }
	    pushdown(x);
	    if(id<=mid) update2(x<<1,l,mid,id,k);
	    else update2(x<<1|1,mid+1,r,id,k);
	    pushup(x);
	}
}
namespace segtree_mx{
	int tr[800001],minn[800001],tag[800001];
	int tp[800001],id[800001];
	void pushup(int x){
	    tr[x]=tr[x<<1]+tr[x<<1|1];
	    minn[x]=1e18,id[x]=0;
	    if(minn[x<<1]<minn[x<<1|1]&&tp[x<<1]) minn[x]=minn[x<<1],id[x]=id[x<<1];
	    else if(tp[x<<1|1]) minn[x]=minn[x<<1|1],id[x]=id[x<<1|1];
	    tp[x]=tp[x<<1]+tp[x<<1|1];
	}
	void pushdown(int x) {
	    if(!tag[x]) return;
	    if(tp[x<<1]){
	        tr[x<<1]+=tp[x<<1]*tag[x]; 
	        minn[x<<1]+=tag[x];
	        tag[x<<1]+=tag[x];
	    }
	    if(tp[x<<1|1]){
	        tr[x<<1|1]+=tp[x<<1|1]*tag[x];
	        minn[x<<1|1]+=tag[x];
	        tag[x<<1|1]+=tag[x];
	    }
	    tag[x]=0;
	}
	void build(int x,int l,int r){
	    if(l==r){
	        tr[x]=a[l],minn[x]=a[l];
	        id[x]=l,tp[x]=1,tag[x]=0;
	        return;
	    }
	    build(x<<1,l,mid);
		build(x<<1|1,mid+1,r);
	    pushup(x);
	}
	int query(int x,int l,int r,int nl,int nr){
	    if(!tp[x]) return 0;
	    if(nl<=l&&r<=nr) return tr[x];
	    pushdown(x);
	    int res=0;
	    if(nl<=mid&&tp[x<<1]) res+=query(x<<1,l,mid,nl,nr);
	    if(nr>mid&&tp[x<<1|1]) res+=query(x<<1|1,mid+1,r,nl,nr);
	    pushup(x);
	    return res;
	}
	void update(int x,int l,int r,int nl,int nr,int k){
	    if(!tp[x]) return;
	    if(l==r&&minn[x]<=-k){
	      tp[x]=tr[x]=id[x]=0;
	      segtree_mn::update2(1,1,n,l,minn[x]);
	      minn[x]=1e18;
	      return;
	    }
	    if(nl<=l&&r<=nr){
	        if(minn[x]<=-k){
		        pushdown(x);
		        if(tp[x<<1]) update(x<<1,l,mid,nl,nr,k);
		        if(tp[x<<1|1]) update(x<<1|1,mid+1,r,nl,nr,k);
		        pushup(x);
		        return;
	        }
	        tr[x]+=tp[x]*k;
	        minn[x]+=k;
	        tag[x]+=k;
	        return;
	    }
	    pushdown(x);
	    if(nl<=mid&&tp[x<<1]) update(x<<1,l,mid,nl,nr,k);
	    if(nr>mid&&tp[x<<1|1]) update(x<<1|1,mid+1,r,nl,nr,k);
	    pushup(x);
	}
}
signed main(){
	int T=read();
	while(T--){
		n=read(),m=read();
		for(int i=1;i<=n;i++) a[i]=read();
		segtree_mx::build(1,1,n);
		segtree_mn::build(1,1,n);
		while(m--){
			int op=read(),l=read(),r=read();
			if(op==1){
				int x=read();
				segtree_mx::update(1,1,n,l,r,-x);
				segtree_mn::update(1,1,n,l,r,x);
			}else{
				int ans=segtree_mx::query(1,1,n,l,r)+segtree_mn::query(1,1,n,l,r);
				write(ans);
				puts("");
			}
		}
	}
	return 0;
}