#include<bits/stdc++.h>
using namespace std;
int n,q,a[300010],len,l[1010],r[1010],id[300010];
long long b1[1010],b2[1010],c[300010];
struct node
{
	mutable int first,second;
	mutable long long v;
	bool operator < (const node &x)const
	{
		if(first==x.first)
		return second<x.second;
		return first<x.first;
	}
};
set<node> s;
void Add(int L,int R,long long y)
{
	b2[id[L]]-=c[L]*L,b2[id[R+1]]-=c[R+1]*(R+1);
	c[L]+=y,c[R+1]-=y;
	b1[id[L]]+=y,b1[id[R+1]]-=y;
	b2[id[L]]+=c[L]*L,b2[id[R+1]]+=c[R+1]*(R+1);
}
long long ask(int L,int R)
{
	long long num=0;
	for(int i=1;i<id[R];i++)
	{
		num+=b1[i]*(R+1)-b2[i];
		if(i<id[L-1])
		num-=b1[i]*L-b2[i];
	}
	for(int i=l[id[L-1]];i<L;i++)
	num-=L*c[i]-i*c[i];
	for(int i=l[id[R]];i<=R;i++)
	num+=(R+1)*c[i]-i*c[i];
	return num;
}
void bh()
{
	set<node>::iterator it=s.begin();
	while(it!=s.end())
	{
		node x=(*it);
		if(x.second!=n)
		{
			if(x.first==x.second)
			it=s.erase(it);
			else
			{
				it->v-=c[it->second];
				it->second--;
				it++;
			}
			Add(x.second,x.second,-x.v);
		}
		else
		it++;
	}
}
int read()
{
	int x=0;
	char c=getchar();
	while(!isdigit(c))
	c=getchar();
	while(isdigit(c))
	{
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x;
}
int main()
{
//	freopen("cin.in","r",stdin);
//	freopen("out.out","w",stdout);
	memset(l,0x3f,sizeof l);
	n=read(),q=read();
	len=700;
	for(int i=1;i<=n;i++)
	{
		id[i]=(i-1)/len+1;
		l[id[i]]=min(l[id[i]],i),r[id[i]]=max(r[id[i]],i);
	}
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		Add(i,i,a[i]);
	}
	s.insert((node){1,n,a[n]});
	while(q--)
	{
		int op;
		op=read();
		if(op==1)
		{
			int x,y;
			x=read(),y=read();
			if(y)
			{
				set<node>::iterator it=s.upper_bound(node{x,500000,0}),itt;
				if(it!=s.begin())
				it--;
				else
				{
					if(it==s.end()||(*it).first>x+1)
					s.insert(node{x,x,y});
					else
					{
						node z=(*it);
						s.erase(it);
						s.insert(node{x,z.second,z.v});
					}
					bh();
					continue;
				}
				if((*it).second>=x)
				{
					if((it->second)==x)
					it->v=y; 
					bh();
					continue;
				}
				itt=it,it++;
				node x1=(*itt),x2=(*it);
				if(x1.second+1==x&&x2.first-1==x)
				{
					it++;
					s.erase(itt,it);
					s.insert(node{x1.first,x2.second,ask(x2.second,x2.second)});
				}
				else if(x1.second+1==x)
				{
					s.erase(itt);
					s.insert(node{x1.first,x,y});
				}
				else if(x2.first-1==x)
				{
					s.erase(it);
					s.insert(node{x,x2.second,x2.v});
				}
				else
				s.insert(node{x,x,y});
			}
			else
			{
				set<node>::iterator it=s.upper_bound(node{x,500000,0}),itt;
				if(it!=s.begin())
				it--;
				else
				{
					bh();
					continue;
				}
				if((*it).second<x)
				{
					bh();
					continue;
				}
				node x1=(*it);
				s.erase(it);
				if(x1.first==x)
				{
					if(x1.first!=x1.second)
					s.insert(node{x1.first+1,x1.second,x1.v});
				}
				else if(x1.second==x)
				s.insert(node{x1.first,x1.second-1,x1.v-c[x1.second]});
				else
				{
					s.insert(node{x1.first,x-1,ask(x-1,x-1)});
					s.insert(node{x+1,x1.second,x1.v});
				}
			}
			Add(x,x,y-ask(x,x));
		}
		else if(op==2)
		{
			int L,R,v;
			L=read(),R=read(),v=read();
			Add(L,R,v);
			set<node>::iterator it1=s.lower_bound(node{L,0,0}),it2=s.upper_bound(node{R,500000,0}),it3;
			if(it2!=s.begin())
			{
				it3=it2;
				it3--;
				R=max(R,(*it3).second);
			}
			s.erase(it1,it2);
			it1=(s.insert(node{L,R,ask(R,R)})).first;
			if(it1!=s.begin())
			{
				it2=it1;
				it1--;
				node x=(*it1);
				if(x.second>=L-1)
				{
					it2++;
					s.erase(it1,it2);
					it1=(s.insert(node{x.first,R,ask(R,R)})).first;
				}
				else
				it1=it2;
			}
			it2=it1,it1++;
			if(it1!=s.end())
			{
				node x=(*it1),y=(*it2);
				if(x.first<=R+1)
				{
					it1++;
					s.erase(it2,it1);
					s.insert(node{y.first,x.second,ask(x.second,x.second)});
				}
			}
		}
		else if(op==3)
		{
			for(set<node>::iterator it=s.begin();it!=s.end();it++)
			{
				node x=(*it);
				Add(x.first,x.second,1);
				it->v++;
			}
		}
		else if(op==4)
		{
			for(set<node>::iterator it=s.begin();it!=s.end();it++)
			{
				node x=(*it);
				Add(x.first,x.second,x.second-x.first+1);
				it->v+=x.second-x.first+1;
			}
		}
		else
		{
			int L,R;
			L=read(),R=read();
			printf("%lld\n",ask(L,R));
		}
		bh();
	}
	return 0;
}