#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e13;
const ll maxn=200025;
const ll maxm=maxn*20;
ll n,m,i,j,t,k,s,a[maxn],op[maxn],lef[maxn],rig[maxn];
ll ord[maxn],stp[maxn],edp[maxn];
ll rt[maxn],ls[maxm],rs[maxm],tot;
ll ki[maxm],bi[maxm],va[maxn];
bool hv[maxm];

inline ll up_div(ll x,ll y){return (x+y-1)/y;}

void upd(ll &nrt,ll ort,ll l,ll r,ll nk,ll nb)
{
	nrt=++tot;ls[nrt]=ls[ort];rs[nrt]=rs[ort];
	if (!hv[ort])
	{
		hv[nrt]=1;ki[nrt]=nk;bi[nrt]=nb;return;
	}
	ki[nrt]=ki[ort];bi[nrt]=bi[ort];hv[nrt]=hv[ort];
	ll mid=(l+r)>>1;
	ll v0=ki[nrt]*mid+bi[nrt],v1=nk*mid+nb;
	if (v0>v1) swap(ki[nrt],nk),swap(bi[nrt],nb);
	if (l<r)
	{
		if (ki[nrt]*l+bi[nrt]>nk*l+nb)
		 upd(ls[nrt],ls[ort],l,mid-1,nk,nb);
		else if (ki[nrt]*r+bi[nrt]>nk*r+nb)
		 upd(rs[nrt],rs[ort],mid+1,r,nk,nb);
	}
}
ll query(ll rt,ll l,ll r,ll pl)
{
	if (!hv[rt]) return INF;
	if (l==r) return ki[rt]*pl+bi[rt];
	ll mid=(l+r)>>1;
	return min(ki[rt]*pl+bi[rt],
	 (pl>mid?query(rs[rt],mid+1,r,pl):query(ls[rt],l,mid,pl)));
}

void erfen(ll l,ll r,ll L,ll R)
{
	if (L>R){for (ll i=l;i<=r;++i) stp[i]=L,edp[i]=R;return;}
	if (l==r){stp[l]=L;edp[l]=R;return;}
	ll mid=(l+r)>>1,p=L-1;
	for (ll i=L;i<=R;++i)
	{
		ll tmp=query(rt[mid],1,n,ord[i]);
		if (tmp<a[ord[i]])
		{
			++p;swap(ord[i],ord[p]);
		}
	}
	erfen(l,mid,L,p);erfen(mid+1,r,p+1,R);
}

ll lit[maxn<<2];
ll val[maxn<<2],sum[maxn<<2],tgk[maxn<<2],tgb[maxn<<2];
bool hvtg[maxn<<2];

inline void pushdown(ll rt)
{
	if (hvtg[rt])
	{
		hvtg[rt<<1]=hvtg[rt<<1|1]=1;hvtg[rt]=0;
		tgk[rt<<1]=tgk[rt<<1|1]=tgk[rt];
		tgb[rt<<1]=tgb[rt<<1|1]=tgb[rt];
		sum[rt<<1]=lit[rt<<1]*tgb[rt]+tgk[rt]*val[rt<<1];
		sum[rt<<1|1]=lit[rt<<1|1]*tgb[rt]+tgk[rt]*val[rt<<1|1];
		tgk[rt]=tgb[rt]=0;
	}
}

void updlit(ll rt,ll l,ll r,ll pl,ll vv)
{
	if (l==r)
	{
		sum[rt]=vv;val[rt]=r;lit[rt]=1;
		//printf("ohh lit %lld %lld\n",pl,vv);
		return;
	}
	pushdown(rt);ll mid=(l+r)>>1;
	if (pl<=mid) updlit(rt<<1,l,mid,pl,vv);
	else updlit(rt<<1|1,mid+1,r,pl,vv);
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
	val[rt]=val[rt<<1]+val[rt<<1|1];
	lit[rt]=lit[rt<<1]+lit[rt<<1|1];
}
void updtag(ll rt,ll l,ll r,ll L,ll R,ll kk,ll bb)
{
	if (l>=L&&r<=R)
	{
		hvtg[rt]=1;tgk[rt]=kk;tgb[rt]=bb;
		sum[rt]=bb*lit[rt]+kk*val[rt];
		
		return;
	}
	pushdown(rt);ll mid=(l+r)>>1;
	if (L<=mid) updtag(rt<<1,l,mid,L,R,kk,bb);
	if (R>mid) updtag(rt<<1|1,mid+1,r,L,R,kk,bb);
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
	val[rt]=val[rt<<1]+val[rt<<1|1];
	lit[rt]=lit[rt<<1]+lit[rt<<1|1];
}
ll query_hul(ll rt,ll l,ll r,ll L,ll R)
{
	if (l>=L&&r<=R) return sum[rt];
	pushdown(rt);ll mid=(l+r)>>1;
	if (R<=mid) return query_hul(rt<<1,l,mid,L,R);
	if (L>mid) return query_hul(rt<<1|1,mid+1,r,L,R);
	return query_hul(rt<<1,l,mid,L,R)+
	 query_hul(rt<<1|1,mid+1,r,L,R);
}

ll tr[maxn];

inline void tradd(ll x,ll y){for(;x<=n;x+=(x&(-x)))tr[x]+=y;}
inline ll trqry(ll x)
{
	ll ret=0;//printf("%lld\n",x);
	for (;x;x-=(x&(-x))) ret+=tr[x];
	return ret;
}

ll vk[maxn],vb[maxn];ll tp;

int main()
{
	bi[0]=INF;hv[0]=0;
	scanf("%lld%lld",&n,&m);
	for (i=1;i<=n;++i) scanf("%lld",&a[i]);
	t=0;
	for (i=1;i<=m;++i)
	{
		scanf("%lld",&op[i]);
		rt[i]=rt[i-1];
		if (op[i]==1)
		{
			scanf("%lld",&va[i]);
			upd(rt[i],rt[i-1],1,n,-t,va[i]);
		}
		else if (op[i]==3)
		{
			scanf("%lld%lld",&lef[i],&rig[i]);
		}
		else
		{
			++t;
		}
	}
	for (i=1;i<=n;++i) ord[i]=i;
	erfen(0,m,1,n);//printf("assdadas\n");
	for (i=1;i<=n;++i)
	{
		tr[i]+=a[i];
		if (i+(i&(-i))<=n) tr[i+(i&(-i))]+=tr[i];
	}
	t=0;tp=0;
	/*for (i=0;i<=m;++i)
	{
		printf("%lld      ",i);
		for (j=stp[i];j<=edp[i];++j) printf("%lld ",ord[j]);
		puts("");
	}*/
	for (i=1;i<=m;++i)
	{
		//printf("#%lld\n",i);
		if (op[i]==1)
		{
			// -t,va[i]
			if (tp&&vk[tp]*n+vb[tp]<=-t*1ll*n+va[i])
			 continue;
			if (tp&&vk[tp]==t)
			{
				if (vb[tp]>va[i]) --tp;
				else continue;
			}
			while(tp)
			{
				if (tp==1)
				{
					if (vk[1]+vb[1]>va[i]-t) --tp;
					break;
				}
				else if ((vb[tp]-vb[tp-1])*(vk[tp-1]+t)
				 <(va[i]-vb[tp-1])*(vk[tp-1]-vk[tp])) break;
				--tp;
			}
			k=(!tp?1:up_div(va[i]-vb[tp],vk[tp]+t));
			vb[++tp]=va[i];vk[tp]=-t;
			//printf("aoaoao %lld\n",k);
			updtag(1,1,n,k,n,-t,va[i]);
			for (j=stp[i];j<=edp[i];++j)
			{
				updlit(1,1,n,ord[j],va[i]-t*1ll*ord[j]);
				tradd(ord[j],-a[ord[j]]);
				//printf("col %lld\n",ord[j]);
			}
			//for (j=1;j<=tp;++j)
			// printf("%lld %lld\n",vk[j],vb[j]);
		}
		//chg stp[i-1] - > edp[i-1]
		else if (op[i]==2) ++t;
		else
		{
			//printf("asdas\n");
			ll ans=trqry(rig[i])-trqry(lef[i]-1);
			//printf("%lld ",ans);
			ans+=query_hul(1,1,n,lef[i],rig[i]);
			//printf("%lld ",ans);
			ans+=1ll*(lef[i]+rig[i])*(rig[i]-lef[i]+1)/2ll*t;
			printf("%lld\n",ans);
		}
	}
	return 0;
}