#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5,T=1000,B=256,K=2e9,R=4e4;
struct msg{
	ll lsm,rsm,sm,he;
	friend msg operator+(msg a,msg b){
		msg c;
		c.lsm=max(a.lsm,a.he+b.lsm);
		c.rsm=max(b.rsm,b.he+a.rsm);
		c.he=a.he+b.he;
		c.sm=max(a.sm,b.sm);
		c.sm=max(c.sm,a.rsm+b.lsm);
		return c;
	}
}rs[N],rr[N];
msg to(int x){
	if(x>0)return {x,x,x,x};
	return {0,0,0,x};
}
struct ask{
	int op,l,r,x;
}g[N];
struct Msg{
	ll x;
	int bh;
	friend bool operator<(Msg a,Msg b){
		return a.x<b.x;
	}
}gs[N],ps[N];
struct pt{
	int x;
	ll y;
	friend pt operator-(pt a,pt b){
		return {a.x-b.x,a.y-b.y};
	}
	friend pt operator+(pt a,pt b){
		return {a.x+b.x,a.y+b.y};
	}
}bk[N],tmp[N];
inline ll cro(pt a,pt b){
	return a.x*b.y-a.y*b.x;
}
int n,m,w[N],bh[N],st[N],ed[N],k,idx,sm[B+5],cnt[B+5];
struct node{
	int l,r,laz,tl1,tl2,tl;
	ll sm;
	pt *f1,*f2,*f;
}p[T<<2];
inline pt *cr(int x){
	pt *to=&bk[idx];
	to[0]={0,0};
	idx+=x+1;
	return to;
}
inline void hb1(pt*f,pt*fl,pt*fr,int &tl,int tl1,int tl2,ll sm,int sz){
	tl=0;
	for(int i=1;i<=tl1;i++)f[++tl]=fl[i];
	for(int i=1;i<=tl2;i++){
		pt c=fr[i];
		c.x+=sz;c.y+=sm;
		while(tl&&cro(f[tl-1]-f[tl],c-f[tl])<=0)tl--;
		f[++tl]=c;
	}
}
inline void hb2(pt*f,pt*fl,pt*fr,int &tl,int tl1,int tl2,ll sm,int sz){
	tl=0;
	for(int i=1;i<=tl2;i++)f[++tl]=fr[i];
	for(int i=1;i<=tl1;i++){
		pt c=fl[i];
		c.x+=sz;c.y+=sm;
		while(tl&&cro(f[tl-1]-f[tl],c-f[tl])<=0)tl--;
		f[++tl]=c;
	}
}
inline void hb(pt*f,pt*fl,pt*fr,int&tl,int tl1,int tl2){
	int a=1,b=1;
	tl=0;
	while(a<=tl1||b<=tl2){
		if(b>tl2||(a<=tl1&&cro(fl[a]-fl[a-1],fr[b]-fr[b-1])<0)){
			tl++;
			f[tl]=f[tl-1]+(fl[a]-fl[a-1]);
			a++;
		}else{
			tl++;
			f[tl]=f[tl-1]+(fr[b]-fr[b-1]);
			b++;
		}
	}
}
inline void ist(pt*f,int&tl,pt x){
	while(tl&&cro(f[tl-1]-f[tl],x-f[tl])<=0)tl--;
	f[++tl]=x;
}
inline void chk(pt*f,pt*g,int&tl,int ts){
	int t=0,a=1,b=1;
	while(a<=tl||b<=ts){
		if(a<=tl&&b<=ts&&f[a].x==g[b].x){
			if(f[a].y>g[b].y)ist(tmp,t,f[a]);
			else ist(tmp,t,g[b]);
			a++;b++;
		}else if(b>ts||(a<=tl&&(f[a].x<g[b].x))){
			ist(tmp,t,f[a]);
			a++;
		}else{
			ist(tmp,t,g[b]);
			b++;
		}
	}
	tl=t;
	for(int i=1;i<=tl;i++)f[i]=tmp[i];
}
inline void upset(int x){
	p[x].sm=p[x<<1].sm+p[x<<1|1].sm;
	hb1(p[x].f1,p[x<<1].f1,p[x<<1|1].f1,p[x].tl1,p[x<<1].tl1,p[x<<1|1].tl1,p[x<<1].sm,p[x<<1].r-p[x<<1].l+1);
	hb2(p[x].f2,p[x<<1].f2,p[x<<1|1].f2,p[x].tl2,p[x<<1].tl2,p[x<<1|1].tl2,p[x<<1|1].sm,p[x<<1|1].r-p[x<<1|1].l+1);
    hb(p[x].f,p[x<<1].f2,p[x<<1|1].f1,p[x].tl,p[x<<1].tl2,p[x<<1|1].tl1);
	chk(p[x].f,p[x<<1].f,p[x].tl,p[x<<1].tl);
    chk(p[x].f,p[x<<1|1].f,p[x].tl,p[x<<1|1].tl);
}
inline void add(pt*f,int tl,ll sm){
	for(int i=1;i<=tl;i++)f[i].y+=sm*f[i].x;
}
inline void add(int x,int sm){
	p[x].laz+=sm;
	p[x].sm+=1ll*sm*(p[x].r-p[x].l+1);
	add(p[x].f1,p[x].tl1,sm);
	add(p[x].f2,p[x].tl2,sm);
	add(p[x].f,p[x].tl,sm);
}
inline void dnset(int x){
	if(p[x].laz){
		add(x<<1,p[x].laz);
		add(x<<1|1,p[x].laz);
		p[x].laz=0;
	}
}
void reset(int x,int l,int r){
	p[x].l=l,p[x].r=r;
	p[x].f1=cr(r-l+1);p[x].f2=cr(r-l+1);
	p[x].f=cr(r-l+1);
	p[x].laz=0;
	if(l==r){
		p[x].tl1=p[x].tl2=p[x].tl=1;
		p[x].f1[1]=p[x].f2[1]=p[x].f[1]={1,w[l]};
		p[x].sm=w[l];
		return;
	}
	int mid=l+r>>1;
	reset(x<<1,l,mid);
	reset(x<<1|1,mid+1,r);
	upset(x);
}
void add(int x,int l,int r,int sm){
	if(l<=p[x].l&&r>=p[x].r){
		add(x,sm);
		return;
	}
	int mid=p[x].l+p[x].r>>1;
	dnset(x);
	if(l<=mid)add(x<<1,l,r,sm);
	if(r>mid)add(x<<1|1,l,r,sm);
	upset(x);
}
ll val(pt a,int b){
	return a.y+1ll*a.x*b;
}
void Solve1(){
	int nw=0;
	for(int i=1;i<=k;i++){
		while(nw<p[1].tl1&&val(p[1].f1[nw],gs[i].x)<val(p[1].f1[nw+1],gs[i].x))nw++;
		rr[gs[i].bh].lsm=val(p[1].f1[nw],gs[i].x);
	}
}
void Solve2(){
	int nw=0;
	for(int i=1;i<=k;i++){
		while(nw<p[1].tl2&&val(p[1].f2[nw],gs[i].x)<val(p[1].f2[nw+1],gs[i].x))nw++;
		rr[gs[i].bh].rsm=val(p[1].f2[nw],gs[i].x);
	}
}
void Solve(){
	int nw=0;
	for(int i=1;i<=k;i++){
		while(nw<p[1].tl&&val(p[1].f[nw],gs[i].x)<val(p[1].f[nw+1],gs[i].x))nw++;
		rr[gs[i].bh].sm=val(p[1].f[nw],gs[i].x);
	}
}
void solve(){
	for(int i=1;i<=k;i++)gs[i].x+=K;
	for(int i=0;i<32;i+=8){
		for(int j=0;j<B;j++)sm[j]=cnt[j]=0;
		for(int j=1;j<=k;j++)sm[gs[j].x>>i&B-1]++;
		for(int j=1;j<B;j++)sm[j]+=sm[j-1];
		for(int j=1;j<=k;j++){
			int c=gs[j].x>>i&B-1;
			if(c)ps[sm[c-1]+(++cnt[c])]=gs[j];
			else ps[++cnt[0]]=gs[j];
		}
		for(int j=1;j<=k;j++)gs[j]=ps[j];
	}
	for(int i=1;i<=k;i++)gs[i].x-=K;
	Solve1();
	Solve2();
	Solve();
	for(int i=1;i<=k;i++){
		rr[gs[i].bh].he=p[1].sm+1ll*gs[i].x*(p[1].r-p[1].l+1);
		rs[gs[i].bh]=rs[gs[i].bh]+rr[gs[i].bh];
	}
	k=0;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=1;i<=n;i++)bh[i]=(i-1)/T+1;
	for(int i=1;i<=bh[n];i++)st[i]=ed[i-1]+1,ed[i]=min(i*T,n);
	for(int i=1;i<=m;i++){
		int op,l,r,x;
		cin>>op>>l>>r;
		if(op==1)cin>>x;
		g[i]={op,l,r,x};
	}
	for(int i=1;i<=bh[n];i++){
		int cs=0;
		for(int j=1;j<=m;j++){
			if(g[j].op==1){
				if(!(g[j].l<=st[i]&&g[j].r>=ed[i]))cs++;
			}
		}
		if(cs>R){
			for(int j=1;j<=m;j++){
				if(g[j].op==1){
					for(int t=max(g[j].l,st[i]);t<=min(g[j].r,ed[i]);t++)w[t]+=g[j].x;
				}else{
					for(int t=max(g[j].l,st[i]);t<=min(g[j].r,ed[i]);t++)rs[j]=rs[j]+to(w[t]);
				}
			}
			continue;
		}
		idx=0;
		reset(1,st[i],ed[i]);
		ll nw=0;
		for(int j=1;j<=m;j++){
		    if(g[j].l>ed[i]||g[j].r<st[i])continue;
			if(g[j].op==1){
				if(g[j].l<=st[i]&&g[j].r>=ed[i])nw+=g[j].x;
				else{
					solve();
					add(1,nw);
					add(1,max(g[j].l,st[i]),min(g[j].r,ed[i]),g[j].x);
					for(int t=st[i];t<=ed[i];t++)w[t]+=nw;
					for(int t=max(g[j].l,st[i]);t<=min(g[j].r,ed[i]);t++)w[t]+=g[j].x;
					nw=0;
				}
			}else{
				if(g[j].l<=st[i]&&g[j].r>=ed[i])gs[++k]={nw,j};
			    else for(int t=max(g[j].l,st[i]);t<=min(g[j].r,ed[i]);t++)rs[j]=rs[j]+to(w[t]+nw);
			}
		}
		solve();
	}
	for(int i=1;i<=m;i++)if(g[i].op==2)cout<<rs[i].sm<<"\n";
}