#include<bits/stdc++.h>
#define LL long long
#define int LL
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
namespace IO
{
	const int _Pu=2e7+5,_d=32;
	char buf[_Pu],obuf[_Pu],*p1=buf+_Pu,*p2=buf+_Pu,*p3=obuf,*p4=obuf+_Pu-_d;
	inline void fin()
	{
		memmove(buf,p1,p2-p1);
		int rlen=fread(buf+(p2-p1),1,p1-buf,stdin);
		if(p1-rlen>buf) buf[p2-p1+rlen]=EOF;p1=buf;
	}
	inline void fout(){fwrite(obuf,p3-obuf,1,stdout),p3=obuf;}
	inline int rd()
	{
		if(p1+_d>p2) fin();int isne=0,x=0;
		for(;!isdigit(*p1);++p1) isne=(*p1=='-');x=(*p1++-'0');
	    for(;isdigit(*p1);++p1) x=x*10+(*p1-'0');
		if(isne) x=-x;return x;
	}
	inline void wr(LL x,char end='\n')
	{
		if(!x) return *p3++='0',*p3++=end,void();
		if(x<0) *p3++='-',x=-x;
		char sta[20],*top=sta;
		do{*top++=(x%10)+'0';x/=10;}while(x);
		do{*p3++=*--top;}while(top!=sta);(*p3++)=end;
	}
}using IO::rd;using IO::wr;
const int N=2e5+5;
struct node{int l,r,x;}q[N],Q[N];
int T,n,m,a[N];
#define ls (wz<<1)
#define rs (wz<<1|1)
namespace SGT1
{
	struct node{int x;LL lt,s,mn;}a[N<<2];LL x;
	inline void pushup(int wz){a[wz].x=a[ls].x+a[rs].x,a[wz].s=a[ls].s+a[rs].s;a[wz].mn=min(a[ls].mn,a[rs].mn);}
	inline void upd(int wz,int x){a[wz].lt+=x;a[wz].s-=x*a[wz].x;a[wz].mn-=x;}
	inline void pushdown(int wz){LL t=a[wz].lt;upd(ls,t);upd(rs,t);a[wz].lt=0;}
	void build(int l,int r,int wz)
	{
		if(l==r) return a[wz]={1,0,::a[l],::a[l]},void();
		int mid=(l+r)>>1;build(l,mid,ls);build(mid+1,r,rs);
		pushup(wz);
	}
	void updata(int l,int r,int wz,int L,int R,int x)
	{
		if(L<=l&&r<=R) return upd(wz,x);
		int mid=(l+r)>>1;pushdown(wz);
		if(L<=mid) updata(l,mid,ls,L,R,x);
		if(mid<R) updata(mid+1,r,rs,L,R,x);pushup(wz);
	}
	int qp(int l,int r,int wz)
	{
		if(l==r) return x=a[wz].mn,l;int mid=(l+r)>>1;pushdown(wz);
		if(a[ls].mn<0) return qp(l,mid,ls);return qp(mid+1,r,rs);
	}
	void del(int l,int r,int wz,int x)
	{
		if(l==r) return a[wz]={0,0,0,(LL)1e18},void();
		int mid=(l+r)>>1;pushdown(wz);
		if(x<=mid) del(l,mid,ls,x);else del(mid+1,r,rs,x);
		pushup(wz);
	}
	LL query(int l,int r,int wz,int L,int R)
	{
		if(L<=l&&r<=R) return a[wz].s;
		int mid=(l+r)>>1;LL ans=0;pushdown(wz);
		if(L<=mid) ans+=query(l,mid,ls,L,R);
		if(mid<R) ans+=query(mid+1,r,rs,L,R);return ans;
	}
}
namespace SGT2
{
	struct node1{LL s;int x,y,z;}a[N<<2];//x加法，y乘法，z是个数
	inline void init(){for(int i=1;i<=(n<<2);i++) a[i]={0,0,1,0};}
	inline void pushup(int wz){a[wz].z=a[ls].z+a[rs].z,a[wz].s=a[ls].s+a[rs].s;}
	inline void upd(int wz,int x){a[wz].x+=x;a[wz].s+=x*a[wz].z;}
	inline void upd1(int wz,int x){a[wz].x*=x;a[wz].y*=x,a[wz].s*=x;}
	inline void pushdown(int wz){LL t=a[wz].x,t1=a[wz].y;upd1(ls,t1);upd1(rs,t1);upd(ls,t);upd(rs,t);a[wz].x=0,a[wz].y=1;}
	void updata(int l,int r,int wz,int L,int R,int x)
	{
		if(L<=l&&r<=R) return upd1(wz,-1),upd(wz,x);
		int mid=(l+r)>>1;pushdown(wz);
		if(L<=mid) updata(l,mid,ls,L,R,x);
		if(mid<R) updata(mid+1,r,rs,L,R,x);pushup(wz);
	}
	void add(int l,int r,int wz,int p,int x)
	{
		if(l==r) return a[wz]={x,0,1,1},void();
		int mid=(l+r)>>1;pushdown(wz);
		if(p<=mid) add(l,mid,ls,p,x);else add(mid+1,r,rs,p,x);
		pushup(wz);
	}
	LL query(int l,int r,int wz,int L,int R)
	{
		if(L<=l&&r<=R) return a[wz].s;
		int mid=(l+r)>>1;LL ans=0;pushdown(wz);
		if(L<=mid) ans+=query(l,mid,ls,L,R);
		if(mid<R) ans+=query(mid+1,r,rs,L,R);return ans;
	}
}
inline LL que(int l,int r){return SGT1::query(1,n,1,l,r)+SGT2::query(1,n,1,l,r);}
inline void DEL(LL x){LL t;while(SGT1::a[1].mn<0) t=SGT1::qp(1,n,1),SGT1::del(1,n,1,t),SGT2::add(1,n,1,t,SGT1::x+x);}
signed main()
{
	T=rd();
	while(T--)
	{
		n=rd(),m=rd();for(int i=1;i<=n;i++) a[i]=rd();
		for(int i=1,o,l,r,x;i<=m;i++) o=rd(),l=rd(),r=rd(),q[i]={l,r,(o==1)?rd():-1};
		SGT1::build(1,n,1);SGT2::init();
		for(int i=1;i<=m;i++)
		{
			if(q[i].x==-1){wr(que(q[i].l,q[i].r));continue;}
			SGT1::updata(1,n,1,q[i].l,q[i].r,q[i].x);DEL(q[i].x);SGT2::updata(1,n,1,q[i].l,q[i].r,q[i].x);
		}
		for(int i=1;i<=(n<<2);i++) SGT1::a[i]={0,0,0,0},SGT2::a[i]={0,0,0,0};
	}
	return IO::fout(),0;
}