#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int mxn = 200000;
int n, q;
ll a[mxn];

struct segTree{
	int l, r;
	segTree *tl, *tr;
	ll vl, lz, mn1, mn2, mnz, mx1, mx2, mxz;
	
	segTree(int l, int r) : l(l), r(r){
		vl = lz = mn1 = mn2 = mx1 = mx2 = 0, mnz = mxz = r - l + 1;
		if(l != r){
			int mid = (l + r) / 2;
			tl = new segTree(l, mid);
			tr = new segTree(mid + 1, r);
			pul();
		}else{
			upd(a[l]);
		}
	}
	
	void upd(ll x){
		vl += (r - l + 1) * x;
		lz += x;
		mn1 += x, mn2 += x;
		mx1 += x, mx2 += x;
	}
	
	void updmn(ll x){
		if(x >= mx1) return;
		vl += mxz * (x - mx1), mx1 = x, mn2 = min(mn2, x);
		if(x <= mx2) mn1 = mx2 = x;
	}
	
	void updmx(ll x){
		if(x <= mn1) return;
		vl += mnz * (x - mn1), mn1 = x, mx2 = max(mx2, x);
		if(x >= mn2) mn2 = mx1 = x;
	}
	
	void psh(){
		tl->upd(lz), tr->upd(lz), lz = 0;
		tl->updmn(mx1), tr->updmn(mx1);
		tl->updmx(mn1), tr->updmx(mn1);
	}
	
	void pul(){
		vl = tl->vl + tr->vl;
		
		{
			vector<ll> v = {tl->mn1, tl->mn2, tr->mn1, tr->mn2};
			sort(v.begin(), v.end());
			v.erase(unique(v.begin(), v.end()), v.end());
			mn1 = mn2 = v[0];
			if(v.size() > 1) mn2 = v[1];
			mnz = (tl->mn1 == mn1) * tl->mnz + (tr->mn1 == mn1) * tr->mnz;
		}
		
		{
			vector<ll> v = {tl->mx1, tl->mx2, tr->mx1, tr->mx2};
			sort(v.begin(), v.end(), greater<ll>());
			v.erase(unique(v.begin(), v.end()), v.end());
			mx1 = mx2 = v[0];
			if(v.size() > 1) mx2 = v[1];
			mxz = (tl->mx1 == mx1) * tl->mxz + (tr->mx1 == mx1) * tr->mxz;
		}
	}
	
	void add(int x, int y, ll z){
		if(y < l || r < x) return;
		if(x <= l && r <= y) return upd(z);
		psh();
		tl->add(x, y, z), tr->add(x, y, z);
		pul();
	}
	
	void addmn(int x, int y, ll z){
		if(y < l || r < x) return;
		if(x <= l && r <= y && (z > mx2 || mx1 == mx2)) return updmn(z);
		psh();
		tl->addmn(x, y, z), tr->addmn(x, y, z);
		pul();
	}
	
	void addmx(int x, int y, ll z){
		if(y < l || r < x) return;
		if(x <= l && r <= y && (z < mn2 || mn1 == mn2)) return updmx(z);
		psh();
		tl->addmx(x, y, z), tr->addmx(x, y, z);
		pul();
	}
	
	ll qry(int x, int y){
		if(y < l || r < x) return 0;
		if(x <= l && r <= y) return vl;
		psh();
		return tl->qry(x, y) + tr->qry(x, y);
	}
};

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> q;
	
	for(int i = 0; i < n; i++) cin >> a[i];
	
	segTree tre(0, n - 1);
	while(q--){
		ll t, x, y, z;
		cin >> t >> x >> y; if(t < 3) cin >> z;
		y--;
		switch(t){
			case 0:
				tre.addmn(x, y, z);
				break;
			case 1:
				tre.addmx(x, y, z);
				break;
			case 2:
				tre.add(x, y, z);
				break;
			case 3:
				cout << tre.qry(x, y) << endl;
				break;
		}
	}
	
	return 0;
}