rt

#include<bits/stdc++.h>
#define F(i, l, r) for(int (i) = (l); (i) <= (r); (i) ++)
#define sum(p) tree[p].sum
#define max1(p) tree[p].maxst
#define max2(p) tree[p].maxnd
#define maxhis(p) tree[p].maxhis
#define cnt(p) tree[p].maxnum
#define l(p) tree[p].l
#define r(p) tree[p].r
#define lzy1(p) tree[p].lazy1
#define lzy2(p) tree[p].lazy2
#define lzy3(p) tree[p].lazy3
#define lzy4(p) tree[p].lazy4
#define int long long
using namespace std;
const int N = 5e5+3;
int a[N];
struct STree{
	int sum, maxst, maxnd, maxhis, maxnum, l, r;
	int lazy1, lazy2, lazy3, lazy4;
	void Clear() {
		lazy1 = lazy2 = lazy3 = lazy4 = 0;
	}
}tree[N*4];

void pushup(int p) {
	
	max1(p) = max(max1(p<<1), max1(p<<1|1));
	maxhis(p) = max(maxhis(p<<1), maxhis(p<<1|1));
	sum(p) = sum(p<<1) + sum(p<<1|1);
	
	if(max1(p<<1) == max1(p<<1|1)) {
		
		max2(p) = max(max2(p<<1), max2(p<<1|1) );
		cnt(p) = cnt(p<<1) + cnt(p<<1|1);
		
	}else if(max1(p<<1) > max1(p<<1|1) ) {
		
		max2(p) = max(max1(p<<1|1), max2(p<<1));
		cnt(p) = cnt(p<<1);
			
	}else if(max1(p<<1) < max1(p<<1|1)) {
		
		max2(p) = max(max1(p<<1), max2(p<<1|1));
		cnt(p) = cnt(p<<1|1);
	}
}
void build(int p, int l, int r) {
	l(p) = l; r(p) = r;
	if(l == r) {
		sum(p) = max1(p) = maxhis(p) = a[l];
		max2(p) = -1e18; cnt(p) = 1;
		return;
	}
	int mid = (l+r)>>1;
	build(p<<1, l, mid);
	build(p<<1|1, mid+1, r);
	pushup(p);
}
void updata(int p, int l1, int l2, int l3, int l4)
{
	sum(p) += (l1 * cnt(p) + l3 * (r(p) - l(p) + 1 - cnt(p)));
	maxhis(p) = max(maxhis(p), max1(p) + l2);
	max1(p) += l1;
	if(max2(p) != -1e18) max2(p) += l3;
	lzy2(p) = max(lzy2(p), lzy1(p) + l2), lzy1(p) += l1;
	lzy4(p) = max(lzy4(p), lzy3(p) + l4), lzy3(p) += l3;
}
void pushdown(int p) {
	int maxn = max(max1(p<<1), max1(p<<1|1));
	if(maxn == max1(p<<1) ) {
		updata(p<<1, lzy1(p), lzy2(p), lzy3(p), lzy4(p) );
	}else {
		updata(p<<1, lzy3(p), lzy4(p), lzy3(p), lzy4(p) );
	}if(maxn == max1(p<<1|1) ) {
		updata(p<<1|1, lzy1(p), lzy2(p), lzy3(p), lzy4(p) );
	}else {
		updata(p<<1|1, lzy3(p), lzy4(p), lzy3(p), lzy4(p) );
	}
	tree[p].Clear();
}
int x, y, k;

void modify1(int p) {
	if(l(p) > y || r(p) < x) return;
	if(l(p) >= x && r(p) <= y) {
		updata(p, k, k, k, k);
		return;
	} 
	pushdown(p);
	modify1(p<<1);
	modify1(p<<1|1);
	pushup(p);
}
void modify2(int p) {
	if(l(p) > y || r(p) < x) return;
	if(max1(p) <= k) return;
	if(l(p) >= x && r(p) <= y && max2(p) < k) {
		updata(p, k-max1(p), k-max1(p), 0, 0);
		return;
	}
	pushdown(p);
	modify2(p<<1);
	modify2(p<<1|1);
	pushup(p);
}
int query1(int p) {
	if(l(p) > y || r(p) < x) return 0;
	if(l(p) >= x && r(p) <= y) {
		return sum(p);
	}
	pushdown(p);
	return query1(p<<1)+query1(p<<1|1);
//	if(l(p) >= x && r(p) <= y) {
//		return sum(p);
//	}
//	pushdown(p);
//	int ans = 0;
//	int mid = (l(p) + r(p)) >> 1;
//	if(x <= mid) ans += query1(p<<1);
//	if(y > mid) ans += query1(p<<1|1);
//	return ans;
}
int query2(int p) {
	if(l(p) > y || r(p) < x) return -1e18;
	if(l(p) >= x && r(p) <= y) {
		return max1(p);
	}
	pushdown(p);
	return max(query2(p<<1), query2(p<<1|1));
//	if(l(p) >= x && r(p) <= y) {
//		return max1(p);
//	}
//	pushdown(p);
//	int ans = -1e18;
//	int mid = (l(p) + r(p)) >> 1;
//	if(x <= mid) ans = max(ans, query2(p<<1) );
//	if(y > mid) ans= max(ans, query2(p<<1|1) );
//	return ans;
}
int query3(int p) {
	if(l(p) > y || r(p) < x) return -1e18;
	if(l(p) >= x && r(p) <= y) {
		return maxhis(p);
	}
	pushdown(p);
	return max(query3(p<<1), query3(p<<1|1));
//	int ans = -N;
//	int mid = (l(p) + r(p)) >> 1;
//	if(x <= mid) ans =max(ans, query3(p<<1) );
//	if(y > mid) ans=max(ans, query3(p<<1|1) );
//	return ans;
}
signed main() {
	int n, m;
	cin>>n>>m;
	F(i, 1, n) {
		scanf("%lld", &a[i]);
	}
//	F(i,1, n) cout<<a[i]<<" ";
	build(1, 1, n);
//	F(i, 1, 20) cout<<i<<":"<<sum(i)<<"\n";
	
	F(i, 1, m) {
		int op; scanf("%lld", &op);
		if(op == 1) {
			scanf("%lld%lld%lld", &x, &y, &k);
			modify1(1);
		}else if(op == 2) {
			scanf("%lld%lld%lld", &x, &y, &k);
			modify2(2);
		}else if(op == 3) {
			scanf("%lld%lld", &x, &y);
			printf("%lld\n", query1(1));
		}else if(op == 4) {
			scanf("%lld%lld", &x, &y);
			printf("%lld\n", query2(1));
		}else {
			scanf("%lld%lld", &x, &y);
			printf("%lld\n", query3(1));
		}
	}
	return 0;
}