#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,inf1=1e9;
const ll inf=4e18;
int n,q;
ll a[N];
int K[N],tot;
ll B[N];
bool cmp(int x,int k1,ll b1,int k2,ll b2)
{
	if(1ll*x*k1+b1<1ll*x*k2+b2)return 1;
	return 0;
}
struct BIT
{
	ll t[N];
	int lowbit(int x){return (x&-x);}
	void add(int x,ll v){for(int i=x;i<N;i+=lowbit(i))t[i]+=v;}
	ll ask(int x){ll res=0;for(int i=x;i>=1;i-=lowbit(i))res+=t[i];return res;}
}t1,t2,t4,t5;
struct abc{ll k,b;};
struct Val{abc v;int pos,lst;};
struct Tag{int addx;void clr(){addx=0;}};
bool istg(Tag a){return a.addx;}
int cross(abc a,abc b)
{
    cout<<a.k<<" "<<a.b<<" "<<b.k<<" "<<b.b<<endl;
	if(a.b>b.b || (a.b==b.b && a.k>b.k))swap(a,b);
	if(a.k<=b.k)return inf1;
	return (b.b-a.b)/(a.k-b.k);
}
Val operator + (Val a,Val b)
{
	Val res;
	if(a.v.b>=b.v.b)res.v=a.v,res.pos=a.pos;else res.v=b.v,res.pos=b.pos;
	res.lst=min(cross(a.v,b.v),min(a.lst,b.lst));
    return res;
}
Val operator + (Val a,Tag b)
{
	Val res;
	res.v=(abc){a.v.k,a.v.b+b.addx*a.v.k},res.pos=a.pos,res.lst-=b.addx;
	return res;
}
Tag operator + (Tag a,Tag b){return (Tag){a.addx+b.addx};}
bool iscor[N];
struct Seg_tree
{
	struct STree{int l,r;Val val;Tag tag;}t[N*4];
	void pushup(int p){t[p].val=t[p*2].val+t[p*2+1].val;}
	void update(int p,Tag v){t[p].val=t[p].val+v,t[p].tag=t[p].tag+v;}
	void pushdown(int p){if(istg(t[p].tag))update(p*2,t[p].tag),update(p*2+1,t[p].tag),t[p].tag.clr();}
	void build(int p,int l,int r)
	{
		t[p].l=l,t[p].r=r;
		if(l==r)return t[p].val.v=(abc){l,a[l]},t[p].val.pos=l,t[p].val.lst=inf1,void();
		int mid=l+r>>1;
		build(p*2,l,mid),build(p*2+1,mid+1,r);
        pushup(p);
        cout<<p<<endl;
	}
    void reb(int p)
    {
        if(t[p].val.lst>0)return ;
        pushdown(p),reb(p*2),reb(p*2+1),pushup(p);
    }
    void change(int p,int l,int r,Tag v)
    {
        if(l<=t[p].l && t[p].r<=r)
        {
            update(p,v);
            reb(p);
            return ;
        }
        pushdown(p);
        int mid=t[p].l+t[p].r>>1;
        if(l<=mid)change(p*2,l,r,v);if(mid<r)change(p*2+1,l,r,v);pushup(p);
    }
    void chg(int p,int x)
    {
        if(t[p].l==t[p].r)return iscor[x]=1,t[p].val.v.k=0,t[p].val.v.b=-inf,void();pushdown(p);
        int mid=t[p].l+t[p].r>>1;
        if(x<=mid)chg(p*2,x);else chg(p*2+1,x);pushup(p);
    }
    Val ask(int p,int l,int r)
    {
        cout<<p<<" "<<t[p].l<<" "<<t[p].r<<endl;
        if(l<=t[p].l && t[p].r<=r)return t[p].val;pushdown(p);
        int mid=t[p].l+t[p].r>>1;
        if(l>mid)return ask(p*2+1,l,r);if(mid>=r)return ask(p*2,l,r);
        return ask(p*2,l,r)+ask(p*2+1,l,r);
    }
}t3;
int nowk;
ll ask(int l,int r,int pos)
{
    cout<<l<<" "<<r<<" "<<pos<<" "<<K[pos]<<" "<<B[pos]<<" "<<nowk<<endl;
    if(K[pos]==-nowk)
    {
        while(1)
        {
            cout<<"?"<<endl;
            Val now=t3.ask(1,l,r);
            cout<<"?"<<endl;
            int x=now.pos;
            if(iscor[x])break;
            if(now.v.b<B[pos])break;
            t2.add(x,-a[x]),t4.add(x,1),t5.add(x,x),t3.chg(1,x);
        }
    }
    cout<<l<<" "<<r<<" "<<pos<<" "<<K[pos]<<" "<<B[pos]<<" "<<nowk<<endl;
    int num=t4.ask(r)-t4.ask(l-1);ll sum=t5.ask(r)-t5.ask(l-1);
    return t2.ask(r)-t2.ask(l-1)+sum*K[pos]+num*B[pos];
}
set<pair<pair<int,int>,int> >s;
void add(pair<pair<int,int>,int>x)
{
	int l=x.first.first,r=x.first.second,pos=x.second;
	s.insert({{l,r},pos});
	t1.add(l,ask(l,r,pos));
}
void del(pair<pair<int,int>,int>x)
{
	int l=x.first.first,r=x.first.second,pos=x.second;
	s.erase({{l,r},pos});
	t1.add(l,-ask(l,r,pos));
}
void solve()
{
	int add1=0;
	K[0]=0,B[0]=inf;
    t3.build(1,1,n);
	add({{1,n},0});
    for(int i=1;i<=n;i++)t2.add(i,a[i]);
	while(q--)
	{
		int op,l,r;
		ll b;
		scanf("%d",&op);
		if(op==1)
		{
			scanf("%lld",&b);
			tot++,K[tot]=-add1,B[tot]=b;
			while(s.size())
			{
				auto it=s.rbegin();
				if(cmp((*it).first.first,K[tot],B[tot],K[(*it).second],B[(*it).second]))
				{
					del((*it));
				}
				else break;
			}
			if(!s.size())add({{1,n},tot});
			else
			{
				auto it=s.rbegin();
				int l=(*it).first.first,r=(*it).first.second,pos=(*it).second;
				del({{l,r},pos});
				int L=l,R=r,res=r+1;
				while(L<=R)
				{
					int mid=L+R>>1;
					if(cmp(mid,K[tot],B[tot],K[pos],B[pos]))res=mid,R=mid-1;
					else L=mid+1;
				}
				if(res!=r+1)add({{l,res-1},pos}),add({{res,n},tot});
				else if(res<=n)add({{l,r},pos}),add({{res,n},tot});
				else add({{l,r},pos});
			}
		}
		else if(op==2)add1++,nowk++,t3.change(1,1,n,(Tag){1});
		else
		{
			scanf("%d %d",&l,&r);
			auto L=--s.lower_bound({{l,n+1},n+1}),R=--s.lower_bound({{r,n+1},n+1});
			ll ans=0;
			if((*L).first.first>=(*R).first.first)ans=ask(l,r,(*R).second);
			else
			{
				ans=t1.ask((*R).first.first-1)-t1.ask((*L).first.first);
				ans+=ask(l,(*L).first.second,(*L).second);
				ans+=ask((*R).first.first,r,(*R).second);
			}
			printf("%lld\n",ans+1ll*add1*(l+r)*(r-l+1)/2);
		}
	}
}
int main()
{
	freopen("ds.in","r",stdin);
	// freopen("ds.out","w",stdout);
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    solve();
	return 0;
}