# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
typedef vector<int> vi;
ll a[200010];
vi vec[200010];
struct Query
{
	int op,l,r;
	ll v;
}que[200010];
struct Point
{
	ll x,y;
	int t;
	Point(ll _x=0,ll _y=0,int _t=0):x(_x),y(_y),t(_t){}
	Point operator-(const Point &a)const{return Point(x-a.x,y-a.y);}
	ll operator*(const Point &a)const{return x*a.y-y*a.x;}
	ll calc(ll p){return y-x*p;}
}b[200010],stk[200010];
struct Seg1
{
	ll sum[600010],w[600010],tag[600010];
	void build(int rt,int l,int r)
	{
		if(l==r) return sum[rt]=a[l],w[rt]=l,void();
		int mid=(l+r)/2;
		build(rt*2,l,mid);build(rt*2+1,mid+1,r);
		sum[rt]=sum[rt*2]+sum[rt*2+1];
		w[rt]=w[rt*2]+w[rt*2+1];
	}
	void push(int rt,ll t){tag[rt]+=t;sum[rt]+=t*w[rt];}
	void pushdown(int rt)
	{
		if(!tag[rt]) return;
		push(rt*2,tag[rt]);push(rt*2+1,tag[rt]);
		tag[rt]=0;
	}
	void update(int rt,int l,int r,int x)
	{
		if(l==r) return w[rt]=sum[rt]=0,void();
		pushdown(rt);
		int mid=(l+r)/2;
		if(x<=mid) update(rt*2,l,mid,x);
		else update(rt*2+1,mid+1,r,x);
		sum[rt]=sum[rt*2]+sum[rt*2+1];
		w[rt]=w[rt*2]+w[rt*2+1];
	}
	ll query(int rt,int l,int r,int x,int y)
	{
		if(l>y || r<x) return 0;
		if(x<=l && r<=y) return sum[rt];
		pushdown(rt);
		int mid=(l+r)/2;
		return query(rt*2,l,mid,x,y)+query(rt*2+1,mid+1,r,x,y);
	}
}S1;
struct Seg2
{
	ll sum[600010],cnt[600010],w[600010],tag[600010],add[600010];
	pli minn[600010];
	void build(int rt,int l,int r)
	{
		tag[rt]=-1;minn[rt]={1e18,0};
		if(l==r) return;
		int mid=(l+r)/2;
		build(rt*2,l,mid);build(rt*2+1,mid+1,r);
	}
	void pushtag(int rt,ll t)
	{
		add[rt]=0;tag[rt]=t;sum[rt]=t*cnt[rt];
		if(cnt[rt]) minn[rt].first=t;
	}
	void pushadd(int rt,ll a)
	{
		add[rt]+=a;sum[rt]+=a*w[rt];
		if(cnt[rt]) minn[rt].first+=a*minn[rt].second;
	}
	void pushdown(int rt)
	{
		if(tag[rt]>=0)
		{
			pushtag(rt*2,tag[rt]);pushtag(rt*2+1,tag[rt]);
			tag[rt]=-1;
		}
		if(add[rt])
		{
			pushadd(rt*2,add[rt]);pushadd(rt*2+1,add[rt]);
			add[rt]=0;
		}
	}
	void update(int rt,int l,int r,ll v)
	{
		if(l==r)
		{
			if(minn[rt].first>=v) pushtag(rt,v);
			return;
		}
		pushdown(rt);
		int mid=(l+r)/2;
		if(minn[rt*2+1].first<v) update(rt*2+1,mid+1,r,v);
		else pushtag(rt*2+1,v),update(rt*2,l,mid,v);
		sum[rt]=sum[rt*2]+sum[rt*2+1];
		minn[rt]=min(minn[rt*2],minn[rt*2+1]);
	}
	void update(int rt,int l,int r,int x,ll y)
	{
		if(l==r) return cnt[rt]=1,minn[rt]={y,x},w[rt]=x,sum[rt]=y,void();
		pushdown(rt);
		int mid=(l+r)/2;
		if(x<=mid) update(rt*2,l,mid,x,y);
		else update(rt*2+1,mid+1,r,x,y);
		sum[rt]=sum[rt*2]+sum[rt*2+1];
		minn[rt]=min(minn[rt*2],minn[rt*2+1]);
		cnt[rt]=cnt[rt*2]+cnt[rt*2+1];
		w[rt]=w[rt*2]+w[rt*2+1];
	}
	ll query(int rt,int l,int r,int x,int y)
	{
		if(l>y || r<x) return 0;
		if(x<=l && r<=y) return sum[rt];
		pushdown(rt);
		int mid=(l+r)/2;
		return query(rt*2,l,mid,x,y)+query(rt*2+1,mid+1,r,x,y);
	}
}S2;
void solve(int l,int r,const vi &S)
{
	if(S.empty()) return;
	if(l==r)
	{
		for(int i:S)
			if(b[l].calc(i)<a[i])
				vec[b[l].t].push_back(i);
		return;
	}
	int mid=(l+r)/2,tp=0,cur=1;
	vi L,R;
	for(int i=l;i<=mid;i++)
	{
		while(tp>1 && (b[i]-stk[tp])*(stk[tp]-stk[tp-1])>=0) tp--;
		stk[++tp]=b[i];
	}
	for(int i:S)
	{
		while(cur<tp && stk[cur].calc(i)>stk[cur+1].calc(i)) cur++;
		if(stk[cur].calc(i)<a[i]) L.push_back(i);
		else R.push_back(i);
	}
	for(int i:L)
	{
		bool ok=0;
		for(int j=l;j<=mid;j++) ok|=(b[j].calc(i)<a[i]);
		assert(ok);
	}
	for(int i:R)
	{
		bool ok=0;
		for(int j=l;j<=mid;j++) ok|=(b[j].calc(i)<a[i]);
		assert(!ok);
	}
	solve(l,mid,L);solve(mid+1,r,R);
}
int main()
{
	int n,q,cur=0,cnt=0;
	cin>>n>>q;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=q;i++)
	{
		scanf("%d",&que[i].op);
		if(que[i].op==1) scanf("%lld",&que[i].v);
		else if(que[i].op==3) scanf("%d%d",&que[i].l,&que[i].r);
	}
	for(int i=1;i<=q;i++)
	{
		if(que[i].op==1) b[++cnt]=Point(cur,que[i].v,i);
		else if(que[i].op==2) cur++;
	}
	vi S(n);
	iota(S.begin(),S.end(),1);
	if(cnt) solve(1,cnt,S);
	S1.build(1,1,n);S2.build(1,1,n);
	for(int i=1;i<=q;i++)
	{
		if(que[i].op==1) S2.update(1,1,n,que[i].v);
		else if(que[i].op==2) S1.push(1,1),S2.pushadd(1,1);
		else printf("%lld\n",S1.query(1,1,n,que[i].l,que[i].r)+S2.query(1,1,n,que[i].l,que[i].r));
		for(int j:vec[i]) S1.update(1,1,n,j),S2.update(1,1,n,j,que[i].v);
	}
	return 0;
}