const int MAXN=1e6+5;
int a[MAXN];
int lef[MAXN<<2],rig[MAXN<<2],maxv[MAXN<<2],maxc[MAXN<<2],secv[MAXN<<2],lazy[MAXN<<2];
LL sum[MAXN<<2];
void push_up(int k){
	sum[k]=sum[k<<1]+sum[k<<1|1];
	if(maxv[k<<1]==maxv[k<<1|1]){
		maxv[k]=maxv[k<<1];
		maxc[k]=maxc[k<<1]+maxc[k<<1|1];
		secv[k]=max(secv[k<<1],secv[k<<1|1]);
	}
	else if(maxv[k<<1]>maxv[k<<1|1]){
		maxv[k]=maxv[k<<1];
		maxc[k]=maxc[k<<1];
		secv[k]=max(secv[k<<1],maxv[k<<1|1]);
	}
	else{
		maxv[k]=maxv[k<<1|1];
		maxc[k]=maxc[k<<1|1];
		secv[k]=max(maxv[k<<1],secv[k<<1|1]);
	}
}
void push_tag(int k,int v){
	if(v>=maxv[k])return;
	sum[k]-=1LL*maxc[k]*(maxv[k]-v);
	maxv[k]=lazy[k]=v;
}
void push_down(int k){
	if(~lazy[k]){
		push_tag(k<<1,lazy[k]);
		push_tag(k<<1|1,lazy[k]);
		lazy[k]=-1;
	}
}
void build(int k,int L,int R){
	lef[k]=L,rig[k]=R,lazy[k]=-1;
	int M=L+R>>1;
	if(L==R){
		sum[k]=maxv[k]=a[M];
		secv[k]=-1;
		maxc[k]=1;
		return;
	}
	build(k<<1,L,M);
	build(k<<1|1,M+1,R);
	push_up(k);
}
void update(int k,int L,int R,int v){
	if(maxv[k]<=v)return;
	if(L<=lef[k]&&rig[k]<=R&&secv[k]<v)
	return push_tag(k,v);
	push_down(k);
	int mid=lef[k]+rig[k]>>1;
	if(mid>=L)update(k<<1,L,R,v);
	if(mid<R)update(k<<1|1,L,R,v);
	push_up(k);
}
int query_max(int k,int L,int R){
	if(L<=lef[k]&&rig[k]<=R)return maxv[k];
	push_down(k);
	int mid=lef[k]+rig[k]>>1,vl=-1,vr=-1;
	if(mid>=L)vl=query_max(k<<1,L,R);
	if(mid<R)vr=query_max(k<<1|1,L,R);
	return max(vl,vr);
}
LL query_sum(int k,int L,int R){
	if(L<=lef[k]&&rig[k]<=R)return sum[k];
	push_down(k);
	int mid=lef[k]+rig[k]>>1;
	LL s=0;
	if(mid>=L)s+=query_sum(k<<1,L,R);
	if(mid<R)s+=query_sum(k<<1|1,L,R);
	return s;
}
int main()
{
	int T=read_int();
	while(T--){
		int n=read_int(),q=read_int();
		_rep(i,1,n)a[i]=read_int();
		build(1,1,n);
		int opt,x,y;
		while(q--){
			opt=read_int(),x=read_int(),y=read_int();
			if(opt==0)
			update(1,x,y,read_int());
			else if(opt==1)
			enter(query_max(1,x,y));
			else
			enter(query_sum(1,x,y));
		}
	}
	return 0;
}