只有样例能过（水
想知道合并部分有没有出错

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T>
inline void read(T&x){
	int w=0;x=0;
	char ch = getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') w=1;
		ch = getchar();
	}
	while(ch>='0' && ch<='9'){
		x = (x<<1)+(x<<3)+(ch^48);
		ch = getchar();
	}
	if(w) x=-x;
}
template <typename T,typename...Args>
inline void read(T&t,Args&...args){
	read(t);read(args...);
}
template <typename T>
inline T Min(T x,T y){
	return (x < y ? x : y);
}
template <typename T>
inline T Max(T x,T y){
	return (x > y ? x : y);
}
const int N = 4e5+10;
const ll INF = 1e15;
struct Func{
	ll k,b;
	Func(){
		k = 0; b = 0;
	}
	Func(ll tk,ll tb){
		k = tk; b = tb;
	}
	inline Func operator + (const Func&G) const{
		return Func(k+G.k,b+G.b);
	}
	inline bool operator < (const Func&G) const{
		return (k==G.k && b<G.b) || k<G.k;
	}
	inline ll operator & (const Func&G) const{
		return (G.b-b)/(k-G.k);
	}
	inline void operator += (const ll&G){
		b += k*G;
	}
};
struct Tree{
	Func lx,rx,sum,mx; ll dx;
	Tree(){
		dx = INF;
	}
	Tree(Func tlx,Func trx,Func tsum,Func tmx,ll tdx){
		lx = tlx; rx = trx; sum = tsum; mx = tmx; dx = tdx;
	}
	inline void Merge_lx(Func x,Func y,Tree &tmp) const{
		if(x<y) swap(x,y);
		if(x.b>=y.b) tmp.lx = x;
		else tmp.lx = y,tmp.dx = Min(tmp.dx,x&y);
	}
	inline void Merge_rx(Func x,Func y,Tree &tmp) const{
		if(x<y) swap(x,y);
		if(x.b>=y.b) tmp.rx = x;
		else tmp.rx = y,tmp.dx = Min(tmp.dx,x&y);
	}
	inline void Merge_mx(Func x,Func y,Tree &tmp) const{
		if(x<y) swap(x,y);
		if(x.b>=y.b) tmp.mx = x;
		else tmp.mx = y,tmp.dx = Min(tmp.dx,x&y);
	}
	inline Tree operator + (const Tree&G) const{
		Tree tmp; tmp.dx = Min(dx,G.dx); tmp.sum = sum+G.sum;
		Merge_lx(lx,sum+G.lx,tmp);Merge_rx(G.rx,G.sum+rx,tmp);
		Merge_mx(G.mx,mx,tmp);Merge_mx(tmp.mx,rx+G.lx,tmp);
		return tmp;
	}
	inline void operator += (const ll&G){
		lx += G; rx += G; mx += G; sum += G; dx -= G;
	}
}tr[N*3],ep;
int P=1,DEP=0,st[N*3]; ll tag[N*3];
inline void push_up(int p){
	tr[p] = tr[p<<1]+tr[p<<1|1];
}
inline void cover(int p,ll k){
	tag[p] += k; tr[p] += k;
}
inline void push_down(int p){
	if(!tag[p]) return ;
	cover(p<<1,tag[p]); cover(p<<1|1,tag[p]);
	tag[p] = 0;
}
inline void rebuild(int p,int dep){
	if(tr[p].dx>=0) return ;
	int head = 1,tail = 0;
	st[++tail] = p;
	for(int i=1,j,ttail,pos;i<dep && tail>=head;++i){
		for(j=ttail=tail;j>=head;--j){
			pos = st[j]; push_down(pos);
			if(tr[pos<<1].dx<0) st[++tail]=pos<<1;
			if(tr[pos<<1|1].dx<0) st[++tail]=pos<<1|1;
		}
		head = ttail+1;
	}
	while(head<=tail) push_down(st[head++]);
	while(tail) push_up(st[tail--]);
}
inline void update(int l,int r,ll k){
	l += P-1; r += P+1;
	for(int dep=DEP;dep;--dep) push_down(l>>dep),push_down(r>>dep);
	for(int dep=0;l^1^r;++dep){
		if(~l&1) cover(l^1,k),rebuild(l^1,dep);
		if(r&1) cover(r^1,k),rebuild(r^1,dep);
		l>>=1;r>>=1;
		push_up(l);push_up(r);
	}
	for(l>>=1; l ;l>>=1) push_up(l);
}
inline Tree query(int l,int r){
	l += P-1; r += P+1;
	for(int dep=DEP;dep;--dep) push_down(l>>dep),push_down(r>>dep);
	Tree res;
	for(int dep=0,f=0;l^1^r;++dep){
		if(~l&1){
			rebuild(l^1,dep);
			if(!f) f = 1,res = tr[l^1];
			else res = res+tr[l^1];
		}
		if(r&1){
			rebuild(r^1,dep);
			if(!f) f = 1,res = tr[r^1];
			else res = res+tr[r^1];
		}
		l>>=1;r>>=1;
		push_up(l);push_up(r);
	}
	for(l>>=1; l ;l>>=1) push_up(l);
	return res;
}
inline void debug(){
	for(int i=(1<<(DEP+1))-1;i;--i){
		cout << i <<":" << tr[i].mx.k << " " << tr[i].mx.b << endl;
		cout << "  lx:" << tr[i].lx.k << " " << tr[i].lx.b << endl;
		cout << "  rx:" << tr[i].rx.k << " " << tr[i].rx.b << endl;
		cout << "  sum:" << tr[i].sum.k << " " << tr[i].sum.b << endl;
		cout << "  dx:" << tr[i].dx << endl;
	}
}
int main(){
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
	int n,m;read(n,m);
	while(P<=n+1) P<<=1,++DEP;
	// cout << P << " " << DEP <<endl;
	for(int i=1,x;i<=n;++i){
		read(x);
		tr[i+P] = Tree(Func(1,1ll*x),Func(1,1ll*x),Func(1,1ll*x),Func(1,1ll*x),INF);
	}
	for(int i=P-1;i;--i) tr[i] = tr[i<<1]+tr[i<<1|1];
	// debug();
	for(int i=1,opt,l,r,k;i<=m;++i){
		read(opt,l,r);
		if(opt==1) read(k),update(l,r,1ll*k);
		else printf("%lld\n",Max(query(l,r).mx.b,0ll));
		// debug();
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}