#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,inf=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;
struct abc{ll k,b;};
struct Val{abc v;int pos,lst;};
struct Tag{int addx;void clr(){addx=0;}};
int cross(abc a,abc b)
{
	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=cross(a.v,b.v);
}
Val operator + (Val a,Tag b)
{
	Val res;
	res.v=(abc){a.v.k,a.v.b+b.addx*a.v.k},res.v.pos=a.v.pos,res.lst-=b.addx;
	return res;
}
Tag operator + (Tag a,Tag b){return (Tag){a.addx+b.addx};}
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))udpate(p*2,)}
	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].pos=l,t[p].lst=inf1,void();
		int mid=l+r>>1;
		build(p*2,l,mid),build(p*2+1,mid+1,r),pushup(p);
	}
}t1;
ll ask(int l,int r,int pos)
{
	ll ress=0;
	for(int i=l;i<=r;i++)ress+=min(a[i],1ll*i*K[pos]+B[pos]);
	return ress;
}
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;
	add({{1,n},0});
	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++;
		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]);
	bool fl1=1;
	for(int i=1;i<n;i++)fl1&=(a[i]<=a[i+1]);
	if(n<=5e3 && q<=5e3){work1::solve();return 0;}
	if(fl1){work2::solve();return 0;}
	return 0;
}

answer.code:5:10: error: conflicting declaration ‘const ll inf’
    5 | const ll inf=4e18;
      |          ^~~
answer.code:4:19: note: previous declaration as ‘const int inf’
    4 | const int N=2e5+5,inf=1e9;
      |                   ^~~
answer.code: In function ‘int cross(abc, abc)’:
answer.code:28:28: error: ‘inf1’ was not declared in this scope; did you mean ‘inf’?
   28 |         if(a.k<=b.k)return inf1;
      |                            ^~~~
      |                            inf
answer.code: In function ‘Val operator+(Val, Val)’:
answer.code:36:1: warning: no return statement in function returning non-void [-Wreturn-type]
   36 | }
      | ^
answer.code: In function ‘Val operator+(Val, Tag)’:
answer.code:40:53: error: ‘struct abc’ has no member named ‘pos’
   40 |         res.v=(abc){a.v.k,a.v.b+b.addx*a.v.k},res.v.pos=a.v.pos,res.lst-=b.addx;
      |                                                     ^~~
answer.code:40:61: error: ‘struct abc’ has no member named ‘pos’
   40 |         res.v=(abc){a.v.k,a.v.b+b.addx*a.v.k},res.v.pos=a.v.pos,res.lst-=b.addx;
      |                                                             ^~~
answer.code: In member function ‘void Seg_tree::pushdown(int)’:
answer.code:49:33: error: ‘istg’ was not declared in this scope
   49 |         void pushdown(int p){if(istg(t[p].tag))udpate(p*2,)}
      |                                 ^~~~
answer.code:49:59: error: expected primary-expression before ‘)’ token
   49 |         void pushdown(int p){if(istg(t[p].tag))udpate(p*2,)}
      |                                                           ^
answer.code:49:48: error: ‘udpate’ was not declared in this scope; did you mean ‘update’?
   49 |         void pushdown(int p){if(istg(t[p].tag))udpate(p*2,)}
      |                                                ^~~~~~
      |                                                update
answer.code: In member function ‘void Seg_tree::build(int, int, int)’:
answer.code:53:62: error: ‘struct Seg_tree::STree’ has no member named ‘pos’
   53 |                 if(l==r)return t[p].val.v=(abc){l,a[l]},t[p].pos=l,t[p].lst=inf1,void();
      |                                                              ^~~
answer.code:53:73: error: ‘struct Seg_tree::STree’ has no member named ‘lst’
   53 |                 if(l==r)return t[p].val.v=(abc){l,a[l]},t[p].pos=l,t[p].lst=inf1,void();
      |                                                                         ^~~
answer.code:53:77: error: ‘inf1’ was not declared in this scope; did you mean ‘inf’?
   53 |                 if(l==r)return t[p].val.v=(abc){l,a[l]},t[p].pos=l,t[p].lst=inf1,void();
      |                                                                             ^~~~
      |                                                                             inf
answer.code: At global scope:
answer.code:57:2: error: conflicting declaration ‘Seg_tree t1’
   57 | }t1;
      |  ^~
answer.code:21:2: note: previous declaration as ‘BIT t1’
   21 | }t1,t2;
      |  ^~
answer.code: In function ‘int main()’:
answer.code:143:30: error: ‘work1’ has not been declared
  143 |         if(n<=5e3 && q<=5e3){work1::solve();return 0;}
      |                              ^~~~~
answer.code:144:17: error: ‘work2’ has not been declared
  144 |         if(fl1){work2::solve();return 0;}
      |                 ^~~~~
answer.code: In function ‘void solve()’:
answer.code:86:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   86 |                 scanf("%d",&op);
      |                 ~~~~~^~~~~~~~~~
answer.code:89:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   89 |                         scanf("%lld",&b);
      |                         ~~~~~^~~~~~~~~~~
answer.code:121:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  121 |                         scanf("%d %d",&l,&r);
      |                         ~~~~~^~~~~~~~~~~~~~~
answer.code: In function ‘int main()’:
answer.code:137:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  137 |         freopen("ds.in","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~
answer.code:138:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  138 |         freopen("ds.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
answer.code:139:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  139 |         scanf("%d %d",&n,&q);
      |         ~~~~~^~~~~~~~~~~~~~~
answer.code:140:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared wit...