#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,INF=1e9;
struct TreeNode{int ls,rs,val,len,mn,sum,siz,lazy,randnum;}tr[N<<2];
int n,m,a[N],root,tot,tag[N<<2],ori[N<<2];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int New(int val,int len){
	tr[++tot]={0,0,val,len,val,val*len,len,0,int(rng())};
	return tot;
}
inline void pushup(int p){
	tr[p].mn=min(tr[p].val,min(tr[tr[p].ls].mn,tr[tr[p].rs].mn));
	tr[p].sum=tr[tr[p].ls].sum+tr[tr[p].rs].sum+tr[p].val*tr[p].len;
	tr[p].siz=tr[tr[p].ls].siz+tr[tr[p].rs].siz+tr[p].len;
}
inline void tags(int p,int c){
	if(!p)	return;
	tr[p].lazy+=c,tr[p].val+=c,tr[p].mn+=c;
	tr[p].sum+=c*tr[p].siz;
}
inline void pushdown(int p){
	if(tr[p].lazy)	tags(tr[p].ls,tr[p].lazy),tags(tr[p].rs,tr[p].lazy),tr[p].lazy=0;
}
void split(int p,int num,int &pr,int &qr){
	if(!p){
		pr=qr=0;
		return;
	}
	pushdown(p);
	if(tr[tr[p].ls].siz>=num)	qr=p,split(tr[p].ls,num,pr,tr[p].ls);
	else if(tr[tr[p].ls].siz+tr[p].len>=num){
		if(tr[tr[p].ls].siz+tr[p].len==num)	pr=p,qr=tr[p].rs,tr[p].rs=0;
		else{
			pr=New(tr[p].val,num-tr[tr[p].ls].siz),qr=p;
			tr[p].len=tr[tr[p].ls].siz+tr[p].len-num;
			tr[pr].ls=tr[p].ls,tr[p].ls=0,pushup(pr);
		}
	}
	else	pr=p,split(tr[p].rs,num-tr[tr[p].ls].siz-tr[p].len,tr[p].rs,qr);
	pushup(p);
}
int merge(int p,int q){
	if(!p||!q)  return p|q;
	if(tr[p].randnum>tr[q].randnum){
		pushdown(p);
		tr[p].rs=merge(tr[p].rs,q);
		pushup(p);
		return p;
	}
	else{
		pushdown(q);
		tr[q].ls=merge(p,tr[q].ls);
		pushup(q);
		return q;
	}
}
int find(int p){
	assert(tr[0].mn==INF);
	// assert(p);
	tag[p]=1;
	if(tr[p].val==tr[p].mn){
		tr[p].val=INF;
		pushup(p);
		return p;
	}
	int ret=0;
	pushdown(p);
	if(tr[tr[p].ls].mn==tr[p].mn)	ret=find(tr[p].ls);
	else	ret=find(tr[p].rs);
	pushup(p);
	return ret;
}
void back(int p){
	tag[p]=0;
	if(tr[p].val==INF)	tr[p].val=ori[p];
	pushdown(p);
	if(tag[tr[p].ls])	back(tr[p].ls);
	if(tag[tr[p].rs])	back(tr[p].rs);
	pushup(p);
}
int main(){
	// freopen("in.txt","r",stdin);
	// freopen("out.txt","w",stdout);
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)	cin>>a[i];
	root=tot=0,tr[0].mn=tr[0].val=INF;
	for(int i=1;i<=n;i++)	root=merge(root,New(a[i],1));
	while(m--){
	    int op,l,r,v,L,M,R;
		cin>>op>>l>>r;
		split(root,l-1,L,M),split(M,r-l+1,M,R);
		if(op==1)	cin>>v,M=New(v,r-l+1);
		else if(op==2){
			int mex=-1;
			while(tr[M].mn<=mex+1)	mex=tr[M].mn,ori[find(M)]=mex;
			mex++,back(M),tags(M,mex);
		}
		else	cout<<tr[M].sum<<'\n';
		root=merge(L,merge(M,R));
	}
	return 0;
}