rt,RE+WA+TLE

#include<bits/stdc++.h>
#define int long long
#define lson(x) x<<1
#define rson(x) x<<1|1
using namespace std;
const int N=2e6+5;
int n, m, ans=1145141919810, a[N], tree[N<<2], mx[N<<2], md[N<<2], cnt[N<<2], tag[N<<2];
void pushup(int cur)
{
	tag[cur]=tag[lson(cur)]+tag[rson(cur)];
	if(mx[lson(cur)]==mx[rson(cur)])
	{
		mx[cur]=mx[lson(cur)],cnt[cur]=cnt[lson(cur)]+cnt[rson(cur)],md[cur]=max(md[lson(cur)],md[rson(cur)]);
		return ;
	}
	if(mx[lson(cur)]>mx[rson(cur)])
	{
		mx[cur]=mx[lson(cur)],cnt[cur]=cnt[lson(cur)],md[cur]=max(md[lson(cur)],mx[rson(cur)]);
	}
	else
	{
		mx[cur]=mx[rson(cur)],cnt[cur]=cnt[rson(cur)],md[cur]=max(md[rson(cur)],mx[lson(cur)]);
	}
}
void pushdown(int cur)
{
	if(mx[lson(cur)]>mx[cur]&&md[lson(cur)]<mx[cur])
	{
		tag[lson(cur)]-=(mx[lson(cur)]-mx[cur])*cnt[lson(cur)];
		mx[lson(cur)]=mx[cur];
	}
	if(mx[rson(cur)]>mx[cur]&&md[rson(cur)]<mx[cur])
	{
		tag[rson(cur)]-=(mx[rson(cur)]-mx[cur])*cnt[rson(cur)];
		mx[rson(cur)]=mx[cur];
	}
}
void update(int cur, int lt, int rt, int qx, int qy, int val)
{
	if(mx[cur]<=val)return;
	if(lt>=qx&&rt<=qy&&md[cur]<val)
	{
		tag[cur]-=(mx[cur]-val)*cnt[cur];
		mx[cur]=val;
		return;
	}
	pushdown(cur);
	int mid=(lt+rt)>>1;
	if(qx<=mid)
	{
		update(lson(cur),lt,mid,qx,qy,val);
	}
	if(qy>mid)update(rson(cur),mid+1,rt,qx,qy,val);
	pushup(cur);
}
int query_maxi(int cur, int lt, int rt, int qx, int qy)
{
	if(qx>=lt&&rt<=qy)return mx[cur];
	pushdown(cur);
	int mid=(lt+rt)>>1, ans=0;
	if(qx<=mid)
	{
		ans=max(ans,query_maxi(lson(cur),lt,mid,qx,qy));
	}
	if(qy>mid)
	{
		ans=max(ans,query_maxi(rson(cur),mid+1,rt,qx,qy));
	}
	return ans;
}
int query_all(int cur, int lt, int rt, int qx, int qy)
{
	if(lt>=qx&&rt<=qy)return tag[cur];
	pushdown(cur);
	int mid=(lt+rt)>>1, ans=0;
	if(qx<=mid)
	{
		ans+=max(ans,query_maxi(lson(cur),lt,mid,qx,qy));
	}
	if(qy>mid)
	{
		ans+=max(ans,query_maxi(rson(cur),mid+1,rt,qx,qy));
	}
	return ans;
}
void build(int cur, int l, int r)
{
	if(l==r)
	{
		mx[cur]=tag[cur]=a[l],md[cur]=-1145141919810,cnt[cur]=1;
		return ;
	}
	int mid=(l+r)>>1;
	build(lson(cur),l,mid);
	build(rson(cur),mid+1,r);
	pushup(cur);
}

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t;
	for(cin>>t;t;t--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)cin>>a[i];
		build(1,1,n);
		while(m--)
		{
			int op, l, r;
			cin>>op>>l>>r;
			if(!op)
			{
				int x;
				cin>>x;
				update(1,1,n,l,r,x);
			}
			else if(op==1)
			{
				cout<<query_maxi(1,1,n,l,r)<<"\n";
			}
			else
			{
				cout<<query_all(1,1,n,l,r)<<"\n";
			}
		}
	}
}