#include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;
#define ll long long

int a[N];

struct node{
  ll sum;
  int l, r, maxa, cnt, se, maxb;
  int tag1, tag2, tag3, tag4;  
}tree[N << 2];
#define lc (k * 2)
#define rc (k * 2 + 1)
#define mid (tree[k].l + tree[k].r >> 1)

void pushup(int k){
  tree[k].sum = tree[lc].sum + tree[rc].sum;
  tree[k].maxa = max(tree[lc].maxa, tree[rc].maxa);
  tree[k].maxb = max(tree[lc].maxb, tree[rc].maxb);
  if(tree[lc].maxa == tree[rc].maxa) { tree[k].se = max(tree[lc].se, tree[rc].se); tree[k].cnt = tree[lc].cnt + tree[rc].cnt; }
  else if(tree[lc].maxa > tree[rc].maxa) { tree[k].se = max(tree[lc].se, tree[rc].maxa); tree[k].cnt = tree[lc].cnt; }
  else { tree[k].se = max(tree[lc].maxa, tree[rc].se); tree[k].cnt = tree[rc].cnt; }
}

void build(int k, int l, int r){
  tree[k].l = l, tree[k].r = r;
  if(l == r) { tree[k].sum = tree[k].maxa = tree[k].maxb = a[l]; tree[k].cnt = 1, tree[k].se = -2e9; return; }
  build(lc, l, mid), build(rc, mid + 1, r);
  pushup(k);
}

void add_tag(int k, int k1,int k2,int k3,int k4){
	tree[k].sum += 1ll * k1 * tree[k].cnt + 1ll * k2 * (tree[k].r - tree[k].l + 1 - tree[k].cnt);
	tree[k].maxb = max(tree[k].maxb, tree[k].maxa + k3); tree[k].maxa += k1;
	if(tree[k].se != -2e9) tree[k].se += k2;
	tree[k].tag3 = max(tree[k].tag3, tree[k].tag1 + k3);
	tree[k].tag4 = max(tree[k].tag4, tree[k].tag2 + k4);
	tree[k].tag1 += k1, tree[k].tag2 += k2;
}

void pushdown(int k) {
	int maxn = max(tree[k * 2].maxa, tree[k * 2 + 1].maxa);
	if(tree[lc].maxa == maxn) add_tag(lc, tree[k].tag1, tree[k].tag2, tree[k].tag3, tree[k].tag4);
	else add_tag(lc, tree[k].tag2, tree[k].tag2, tree[k].tag4, tree[k].tag4);
	if(tree[rc].maxa == maxn) add_tag(rc, tree[k].tag1, tree[k].tag2, tree[k].tag3, tree[k].tag4);
	else add_tag(rc, tree[k].tag2, tree[k].tag2, tree[k].tag4, tree[k].tag4);
	tree[k].tag1 = tree[k].tag2 = tree[k].tag3 = tree[k].tag4 = 0;
}

void mod_add(int k, int l, int r, int v){
  if(tree[k].l >= l && tree[k].r <= r) {
    tree[k].sum += 1ll * v * tree[k].cnt + 1ll * v * (tree[k].r - tree[k].l + 1 - tree[k].cnt);
    tree[k].maxa += v; tree[k].maxb = max(tree[k].maxb, tree[k].maxa);
    if(tree[k].se != -2e9) tree[k].se += v;
    tree[k].tag1 += v, tree[k].tag2 += v;
    tree[k].tag3 = max(tree[k].tag3, tree[k].tag1);
    tree[k].tag4 = max(tree[k].tag4, tree[k].tag2);
    return;
  }
  pushdown(k);
  if(r <= mid) mod_add(lc, l, r, v);
  else if(l > mid) mod_add(rc, l, r, v);
  else mod_add(lc, l, mid, v), mod_add(rc, mid + 1, r, v);
  pushup(k);
}

void mod_min(int k, int l, int r, int v){
  if(v >= tree[k].maxa) return;
  if(tree[k].l >= l && tree[k].r <= r && tree[k].se < v) {
    int det = tree[k].maxa - v;
    tree[k].sum -= 1ll * tree[k].cnt * det;
    tree[k].maxa = v, tree[k].tag1 -= det;
    return;
  } 
  if(tree[k].l >= l && tree[k].r <= r) return;
  pushdown(k);
  if(r <= mid) mod_min(lc, l, r, v);
  else if(l > mid) mod_min(rc, l, r, v);
  else mod_min(lc, l, mid, v), mod_min(rc, mid + 1, r, v);
  pushup(k);
}

ll query_sum(int k, int l, int r){
  if(tree[k].l >= l && tree[k].r <= r) return tree[k].sum;
  pushdown(k);
  if(r <= mid) return query_sum(lc, l, r);
  else if(l > mid) return query_sum(rc, l, r);
  else return query_sum(lc, l, mid) + query_sum(rc, mid + 1, r);
}

int query_maxa(int k, int l, int r){
  if(tree[k].l >= l && tree[k].r <= r) return tree[k].maxa;
  pushdown(k);
  if(r <= mid) return query_maxa(lc, l, r);
  else if(l > mid) return query_maxa(rc, l, r);
  else return max(query_maxa(lc, l, mid), query_maxa(rc, mid + 1, r));
}

int query_maxb(int k, int l, int r){
  if(tree[k].l >= l && tree[k].r <= r) return tree[k].maxb;
  pushdown(k);
  if(r <= mid) return query_maxb(lc, l, r);
  else if(l > mid) return query_maxb(rc, l, r);
  else return max(query_maxb(lc, l, mid), query_maxb(rc, mid + 1, r));
}


void solve(){
  int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) cin >> a[i];
  build(1, 1, n);
  for(int i = 1; i <= m; i++){
    int op, l, r; cin >> op >> l >> r;
    if(op == 1) { int v; cin >> v; mod_add(1, l, r, v); }
    else if(op == 2) { int v; cin >> v; mod_min(1, l, r, v); }
    else if(op == 3) { cout << query_sum(1, l, r) << '\n'; }
    else if(op == 4) { cout << query_maxa(1, l, r) << '\n'; }
    else { cout << query_maxb(1, l, r) << '\n'; }
  }
}

int main(){
  ios::sync_with_stdio(false);
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int t = 1;
  //cin >> t;
  while(t--){
    solve();
  }
  return 0;
}