#include<bits/stdc++.h>
const int B=500;
using namespace std;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
int read(){char c=getchar();int p=0,flg=1;while(c<'0'||c>'9'){if(c=='-') flg=-1;c=getchar();}while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}return p*flg;}
int n,m,a[500010],pos[500010],L[1010],R[1010],sum[1010],add[1010],cov[1010];bitset<500010>flg[1010];
void pushdown(int x){for(int i=L[x];i<=R[x];i++){flg[x].reset(a[i]);if(~cov[x]) a[i]=cov[x];a[i]+=add[x];}cov[x]=-1;add[x]=0;}
void rebuild(int x){sum[x]=0;for(int i=L[x];i<=R[x];i++){sum[x]+=a[i];flg[x].set(a[i]);}}
void cover(int l,int r,int v){
	if(pos[l]==pos[r]){pushdown(pos[l]);for(int i=l;i<=r;i++) a[i]=v;rebuild(pos[l]);return ;}
	pushdown(pos[l]);for(int i=l;i<=R[pos[l]];i++) a[i]=v;rebuild(pos[l]);
	pushdown(pos[r]);for(int i=L[pos[r]];i<=r;i++) a[i]=v;rebuild(pos[r]);
	for(int i=pos[l]+1;i<pos[r];i++){cov[i]=v;add[i]=0;sum[i]=v*(R[i]-L[i]+1);}
}
void upd(int l,int r,int v){
	if(pos[l]==pos[r]){pushdown(pos[l]);for(int i=l;i<=r;i++) a[i]+=v;rebuild(pos[l]);return ;}
	pushdown(pos[l]);for(int i=l;i<=R[pos[l]];i++) a[i]+=v;rebuild(pos[l]);
	pushdown(pos[r]);for(int i=L[pos[r]];i<=r;i++) a[i]+=v;rebuild(pos[r]);
	for(int i=pos[l]+1;i<pos[r];i++){add[i]+=v;sum[i]+=v*(R[i]-L[i]+1);}
}
int find(int l,int r,int v){
	if(pos[l]==pos[r]){for(int i=l;i<=r;i++) if(~cov[pos[l]]){if(cov[pos[l]]+add[pos[l]]==v) return 1;}else if(a[i]+add[pos[l]]==v) return 1;return 0;}
	for(int i=l;i<=R[pos[l]];i++) if(~cov[pos[l]]){if(cov[pos[l]]+add[pos[l]]==v) return 1;}else if(a[i]+add[pos[l]]==v) return 1;
	for(int i=L[pos[l]];i<=r;i++) if(~cov[pos[r]]){if(cov[pos[r]]+add[pos[r]]==v) return 1;}else if(a[i]+add[pos[r]]==v) return 1;
	for(int i=pos[l]+1;i<pos[r];i++) if(~cov[i]){if(cov[i]+add[i]==v) return 1;}else if(v>=add[i]&&flg[i][v-add[i]]) return 1;return 0;
}
int query(int l,int r){
	int ans=0;if(pos[l]==pos[r]){for(int i=l;i<=r;i++) if(~cov[pos[l]]) ans+=cov[pos[l]]+add[pos[l]];else ans+=a[i]+add[pos[l]];return ans;}
	for(int i=l;i<=R[pos[l]];i++) if(~cov[pos[l]]) ans+=cov[pos[l]]+add[pos[l]];else ans+=a[i]+add[pos[l]];
	for(int i=L[pos[r]];i<=r;i++) if(~cov[pos[r]]) ans+=cov[pos[r]]+add[pos[r]];else ans+=a[i]+add[pos[r]];
	for(int i=pos[l]+1;i<pos[r];i++) ans+=sum[i];return ans;
}
signed main(){
	n=read();m=min(read(),100000);for(int i=1;i<=n;i++) a[i]=read(),pos[i]=(i-1)/B+1;
	for(int i=1;i<=pos[n];i++){L[i]=(i-1)*B+1;R[i]=min(i*B,n);cov[i]=-1;rebuild(i);}
	while(m--){
		int opt=read(),l=read(),r=read();
		if(!(opt^1)){int v=read();cover(l,r,v);}else if(!(opt^2)){int mex=0;for(;find(l,r,mex);mex++);upd(l,r,mex);}else cout<<query(l,r)<<'\n';
	}
	return 0;
}