#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=5e5+3,M=1<<20|3,INF=1e9;
ll n,m,a[N],mn[M],mx[M],sum[M],tag[M],clr[M];
vector<array<ll,4>>res;
#define ls (p<<1)
#define rs (p<<1|1)
#define mi ((l+r)>>1)
#define lson ls,l,mi
#define rson rs,mi+1,r
void Up(int p)
{
	sum[p]=sum[ls]+sum[rs];
	mn[p]=min(mn[ls],mn[rs]);
	mx[p]=max(mx[ls],mx[rs]);
}
void Build(int p=1,int l=1,int r=n)
{
	clr[p]=-1;
	if(l==r){mn[p]=mx[p]=sum[p]=a[l];return;}
	Build(lson);Build(rson);Up(p);
}
void Clr(ll d,int p,int l,int r){clr[p]=mn[p]=mx[p]=d;sum[p]=d*(r-l+1);tag[p]=0;}
void Add(ll d,int p,int l,int r){tag[p]+=d;mn[p]+=d;mx[p]+=d;sum[p]+=d*(r-l+1);}
void Down(int p,int l,int r)
{
	if(clr[p]!=-1)Clr(clr[p],lson),Clr(clr[p],rson),clr[p]=-1;
	if(tag[p])Add(tag[p],lson),Add(tag[p],rson),tag[p]=0;
}
void Upd(int L,int R,ll d,int p=1,int l=1,int r=n)
{
	if(L<=l&&r<=R)return Clr(d,p,l,r);
	Down(p,l,r);
	if(L<=mi)Upd(L,R,d,lson);
	if(R>mi)Upd(L,R,d,rson);
	Up(p); 
}
ll Ask(int L,int R,int p=1,int l=1,int r=n)
{
	if(L<=l&&r<=R)return sum[p];
	Down(p,l,r);
	if(R<=mi)return Ask(L,R,lson);
	if(L>mi)return Ask(L,R,rson);
	return Ask(L,R,lson)+Ask(L,R,rson);
}
ll Mn(int L,int R,int p=1,int l=1,int r=n)
{
	if(L<=l&&r<=R)return mn[p];
	Down(p,l,r);
	if(R<=mi)return Mn(L,R,lson);
	if(L>mi)return Mn(L,R,rson);
	return min(Mn(L,R,lson),Mn(L,R,rson));
}
void Dfs(int L,int R,ll d,int p=1,int l=1,int r=n)
{
	if(L<=l&&r<=R)
	{
		if(mn[p]>d)return;
		if(mx[p]==d)
		{
			res.push_back({d,p,l,r});Clr(INF,p,l,r);
			return;
		}
	}
	Down(p,l,r);
	if(L<=mi)Dfs(L,R,d,lson);
	if(R>mi)Dfs(L,R,d,rson);
	Up(p);
}
void Mdf(int L,int R,ll d,int p=1,int l=1,int r=n)
{
	if(L<=l&&r<=R)return Add(d,p,l,r);
	Down(p,l,r); 
	if(L<=mi)Mdf(L,R,d,lson);
	if(R>mi)Mdf(L,R,d,rson);
	Up(p);
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	Build();
	while(m--)
	{
		ll op,l,r,d;cin>>op>>l>>r;
		if(op==1){cin>>d;Upd(l,r,d);continue;}
		if(op==3){cout<<Ask(l,r)<<"\n";continue;}
		ll s=0;res.clear();
		while(Mn(l,r)==s)Dfs(l,r,s++);
		for(auto t:res)Upd(t[2],t[3],t[0]);
		Mdf(l,r,s);
	}
}