#include<bits/stdc++.h>
using namespace std;

constexpr int maxn=1<<18;

int n,q,sz,glb;
long long a[maxn];

namespace BIT
{
struct info
{
	long long a,b;
	void operator+=(const info&rhs){a+=rhs.a,b+=rhs.b;}
	void operator-=(const info&rhs){a-=rhs.a,b-=rhs.b;}
}t[maxn];
void add(int i,const info&v)
{
	for(;i<=n;i+=i&-i) t[i]+=v;
}
info query(int l,int r)
{
	info s{0,0};
	for(;r;r-=r&-r) s+=t[r];
	for(l--;l;l-=l&-l) s-=t[l];
	return s;
}
}

namespace SG2
{
struct node
{
	int l,r,cnt,tag;
	long long mn,mx,id,sum,cov;
	void cover(long long x)
	{
		if(!cnt) return;
		mn=mx=cov=x;
		sum=cnt*x;
		tag=0;
	}
	void add(int x)
	{
		if(!cnt) return;
		mn+=1LL*l*x;
		mx+=1LL*r*x;
		tag+=x;
		sum+=id*x;
	}
}t[maxn*2];
void pushdown(int id)
{
	node &rt=t[id],&l=t[id*2],&r=t[id*2+1];
	if(rt.cov!=-1)
	{
		l.cover(rt.cov);
		r.cover(rt.cov);
		rt.cov=-1;
	}
	if(rt.tag)
	{
		l.add(rt.tag);
		r.add(rt.tag);
		rt.tag=0;
	}
}
long long query(int id,int l,int r,int L,int R)
{
	node &rt=t[id];
	if(l==L&&r==R) return rt.sum;
	pushdown(id);
	int mid=(l+r)>>1;
	if(R<=mid) return query(id*2,l,mid,L,R);
	if(L>mid) return query(id*2+1,mid+1,r,L,R);
	return query(id*2,l,mid,L,mid)+query(id*2+1,mid+1,r,mid+1,R);
}
void pushup(int id)
{
	node &rt=t[id],&l=t[id*2],&r=t[id*2+1];
	rt.mn=l.l?l.mn:r.mn;
	rt.l=l.l?l.l:r.l;
	rt.mx=r.r?r.mx:l.mx;
	rt.r=r.r?r.r:l.r;
	rt.sum=l.sum+r.sum;
}
void chkmin(int id,long long v)
{
	node &rt=t[id];
	if(!rt.cnt||rt.mx<=v) return;
	if(rt.mn>=v)
	{
		rt.cover(v);
		return;
	}
	pushdown(id);
	chkmin(id*2,v);
	chkmin(id*2+1,v);
	pushup(id);
}
void insert(int id,int l,int r,int i,long long v)
{
	node &rt=t[id];
	rt.cnt++;
	rt.id+=i;
	if(l==r)
	{
		rt.l=rt.r=i;
		rt.sum=rt.mn=rt.mx=v;
		return;
	}
	pushdown(id);
	int mid=(l+r)>>1;
	if(i<=mid) insert(id*2,l,mid,i,v);
	else insert(id*2+1,mid+1,r,i,v);
	pushup(id);
}
}

vector<int>upd[maxn];

namespace SG1
{
struct node
{
	int k,ti;
	long long b;
	long long operator()(){return 1LL*k*glb+b;}
}t[maxn*2];
void pushup(int id)
{
	node &rt=t[id],&l=t[id*2],&r=t[id*2+1];
	if(!r.k)
	{
		rt.k=l.k;
		rt.ti=-1;
		rt.b=l.b;
		return;
	}
	if(!l.k||r()>=l())
	{
		rt.k=r.k;
		rt.ti=-1;
		rt.b=r.b;
		return;
	}
	rt.k=l.k,rt.b=l.b;
	long long ed=(l.b-r.b+r.k-l.k-1)/(r.k-l.k);
	if(ed>q)
	{
		rt.ti=-1;
	}
	else if(rt.ti!=ed)
	{
		rt.ti=ed;
		upd[ed].push_back(id);
	}
}
void build()
{
	int i;
	for(i=1;i<=n;i++) t[i+sz-1]={i,0,a[i]};
	for(i=sz-1;i>=1;i--) pushup(i);
}
void chkmin(int i,long long v)
{
	if(i>=sz)
	{
		t[i].k=t[i].b=0;
		i-=sz-1;
		SG2::insert(1,1,sz,i,v);
		BIT::add(i,{-a[i],-i});
	}
	else
	{
		if(t[i*2]()>v) chkmin(i*2,v);
		if(t[i*2+1]()>v) chkmin(i*2+1,v);
		pushup(i);
	}
}
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0);
	int i,op,l,r;
	long long v;
	cin>>n>>q;
	for(i=1;i<=n;i++) cin>>a[i],BIT::add(i,{a[i],i});
	for(sz=1;sz<n;sz*=2);
	SG1::build();
	for(i=1;i<=q;i++)
	{
		cin>>op;
		if(op==1)
		{
			cin>>v;
			SG1::chkmin(1,v);
			SG2::chkmin(1,v);
		}
		else if(op==2)
		{
			SG2::t[1].add(1);
			glb++;
			for(int id:upd[glb])
			{
				if(SG1::t[id].ti!=glb) continue;
				SG1::pushup(id);
				for(id>>=1;id;id>>=1)
				{
					int lstk=SG1::t[id].k;
					SG1::pushup(id);
					if(SG1::t[id].k==lstk) break;
				}
			}
		}
		else
		{
			cin>>l>>r;
			auto tmp=BIT::query(l,r);
			cout<<tmp.b*glb+tmp.a+SG2::query(1,1,sz,l,r)<<'\n';
		}
	}
	return 0;
}