#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];
set<pair<int,int> > s;
void Add(int L,int R,int 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 num1=0,num2=0;
	if(L!=1)
	{
		for(int i=1;i<id[L-1];i++)
		num1+=b1[i]*L-b2[i];
		for(int i=l[id[L-1]];i<L;i++)
		num1+=L*c[i]-i*c[i];
	}
	for(int i=1;i<id[R];i++)
	num2+=b1[i]*(R+1)-b2[i];
	for(int i=l[id[R]];i<=R;i++)
	num2+=(R+1)*c[i]-i*c[i];
	return num2-num1;
}
void bh()
{
	set<pair<int,int> >::iterator it=s.begin();
	while(it!=s.end())
	{
		pair<int,int> x=(*it);
		if(x.second!=n)
		{
			Add(x.second,x.second,-ask(x.second,x.second));
			s.erase(it);
			if(x.first!=x.second)
			{
				it=(s.insert(make_pair(x.first,x.second-1))).first;
				it++;
			}
			else
			it=s.lower_bound(make_pair(x.first,0));
		}
		else
		it++;
	}
}
int main()
{
//	freopen("cin.in","r",stdin);
//	freopen("out.out","w",stdout);
	memset(l,0x3f,sizeof l);
	scanf("%d%d",&n,&q);
	len=sqrt(n);
	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++)
	{
		scanf("%d",&a[i]);
		Add(i,i,a[i]);
	}
	s.insert(make_pair(1,n));
	while(q--)
	{
		int op;
		scanf("%d",&op);
		if(op==1)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			Add(x,x,y-ask(x,x));
			if(y)
			{
				set<pair<int,int> >::iterator it=s.upper_bound(make_pair(x,1e9)),itt;
				if(it!=s.begin())
				it--;
				else
				{
					if(it==s.end()||(*it).first>x+1)
					s.insert(make_pair(x,x));
					else
					{
						int R=(*it).second;
						s.erase(it);
						s.insert(make_pair(x,R));
					}
					bh();
					continue;
				}
				if((*it).second>=x)
				{
					bh();
					continue;
				}
				itt=it,it++;
				pair<int,int> x1=(*itt),x2=(*it);
				if(x1.second+1==x&&x2.first-1==x)
				{
					it++;
					s.erase(itt,it);
					s.insert(make_pair(x1.first,x2.second));
				}
				else if(x1.second+1==x)
				{
					s.erase(itt);
					s.insert(make_pair(x1.first,x));
				}
				else if(x2.first-1==x)
				{
					s.erase(it);
					s.insert(make_pair(x,x2.second));
				}
				else
				s.insert(make_pair(x,x));
			}
			else
			{
				set<pair<int,int> >::iterator it=s.upper_bound(make_pair(x,1e9)),itt;
				if(it!=s.begin())
				it--;
				else
				{
					bh();
					continue;
				}
				if((*it).second<x)
				{
					bh();
					continue;
				}
				pair<int,int> x1=(*it);
				s.erase(it);
				if(x1.first==x)
				{
					if(x1.first!=x1.second)
					s.insert(make_pair(x1.first+1,x1.second));
				}
				else if(x1.second==x)
				s.insert(make_pair(x1.first,x1.second-1));
				else
				{
					s.insert(make_pair(x1.first,x-1));
					s.insert(make_pair(x+1,x1.second));
				}
			}
		}
		else if(op==2)
		{
			int L,R,v;
			scanf("%d%d%d",&L,&R,&v);
			Add(L,R,v);
			set<pair<int,int> >::iterator it1=s.lower_bound(make_pair(L,1e9)),it2=s.upper_bound(make_pair(R,1e9)),it3;
			if(it2!=s.begin())
			{
				it3=it2;
				it3--;
				R=max(R,(*it3).second);
			}
			s.erase(it1,it2);
			it1=(s.insert(make_pair(L,R))).first;
			if(it1!=s.begin())
			{
				it2=it1;
				it1--;
				pair<int,int> x=(*it1);
				if(x.second>=L-1)
				{
					it2++;
					s.erase(it1,it2);
					it1=(s.insert(make_pair(x.first,R))).first;
				}
				else
				it1=it2;
			}
			it2=it1,it1++;
			if(it1!=s.end())
			{
				pair<int,int> x=(*it1),y=(*it2);
				if(x.first<=R+1)
				{
					it1++;
					s.erase(it2,it1);
					s.insert(make_pair(y.first,x.second));
				}
			}
		}
		else if(op==3)
		{
			for(set<pair<int,int> >::iterator it=s.begin();it!=s.end();it++)
			{
				pair<int,int> x=(*it);
				Add(x.first,x.second,1);
			}
		}
		else if(op==4)
		{
			for(set<pair<int,int> >::iterator it=s.begin();it!=s.end();it++)
			{
				pair<int,int> x=(*it);
				Add(x.first,x.second,x.second-x.first+1);
			}
		}
		else
		{
			int L,R;
			scanf("%d%d",&L,&R);
			printf("%lld\n",ask(L,R));
		}
		bh();
	}
	return 0;
}