#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define LC k<<1
#define RC k<<1|1
#define IO cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repn(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = (n) - 1; i >= a; i--)
#define pern(i, a, n) for (int i = n; i >= a; i--)

typedef long long LL;
typedef long double LD;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;
typedef pair<double, double> PDD;
typedef pair<ull, ull> PUU;
typedef pair<LL, LL> PLL;

const int N = 210000;
const int M = 1100000;
const int mod = 1e9+7;
const int inf = (int)1e9;
const LL INF = 1e18;
const double eps = 1e-9;

mt19937_64 Rand((unsigned long long)new char);
#define rand Rand

int n, m, flag;
LL add[M], cov[M], sum[M];
LL a[N], cnt, len1[M], len2[M], al[M], ar[M], tot, num;
PLL rval[M], lval[M];

void update(int k) {
	sum[k] = sum[LC] + sum[RC];
	len1[k] = len1[LC] + len1[RC];
	len2[k] = len2[LC] + len2[RC];
	lval[k] = min(lval[LC], lval[RC]);
	rval[k] = max(rval[RC], rval[LC]);
}
void apply_cov(int k, LL v) {
	sum[k] = len1[k] * v;
	if (lval[k].se) lval[k].fi = v;
	if (rval[k].se) rval[k].fi = v;
	add[k] = 0;
	cov[k] = v;
}
void apply_add(int k, LL v) {
	sum[k] += len2[k] * v;
	if (lval[k].se) lval[k].fi += lval[k].se * v;
	if (rval[k].se) rval[k].fi += rval[k].se * v;
	add[k] += v;
}
void pushdown(int k) {
	if (cov[k] != -1) {
		apply_cov(LC, cov[k]);
		apply_cov(RC, cov[k]);
		cov[k] = -1;
	}
	if (add[k]) {
		apply_add(LC, add[k]);
		apply_add(RC, add[k]);
		add[k] = 0;
	}
}
void build(int k, int l, int r) {
	al[k] = l, ar[k] = r;
	cov[k] = -1;
	if (l == r) {
		// sum[k] = a[l];
		// len1[k] = 1;
		// len2[k] = l;
		lval[k] = mp(INF, 0);
		rval[k] = mp(-INF, 0);
		return;
	}
	int mid = (l + r) / 2;
	build(LC, l, mid);
	build(RC, mid + 1, r);
	update(k);
}
void maintain(int k, int l, int r, int x) {
	if (l == r) {
		sum[k] = a[l];
		len1[k] = 1;
		len2[k] = l;
		lval[k] = rval[k] = mp(a[l], l);
		return;
	}
	pushdown(k);
	int mid = (l + r) / 2;
	if (x <= mid) maintain(LC, l, mid, x);
	else maintain(RC, mid + 1, r, x);
	update(k);
}
void change(int k, int l, int r, LL v) {
	if (rval[k].fi <= v) return;
	if (lval[k].fi >= v) {
		apply_cov(k, v);
		return;
	}
	pushdown(k);
	int mid = (l + r) / 2;
	if (lval[RC].fi <= v) change(RC, mid + 1, r, v);
	else apply_cov(RC, v), change(LC, l, mid, v);
	update(k);
}
LL ask(int k, int l, int r, int a, int b) {
	if (l == a && r == b) return sum[k];
	int mid = (l + r) / 2;
	pushdown(k);
	if (b <= mid) return ask(LC, l, mid, a, b);
	else if (a > mid) return ask(RC, mid + 1, r, a, b);
	else return ask(LC, l, mid, a, mid) + ask(RC, mid + 1, r, mid + 1, b);
}
struct line { // y = kx + b;
	LL k, b;
	int id;
	line () {}
	line (LL _k, LL _b, int _id) {
		k = _k, b = _b, id = _id;
	}
	LL val(LL x) {
		return k * x + b;
	}
}tr[M];

void insert(int k, int l, int r, int a, int b, line c) {
	if (l == a && r == b) {
		if (tr[k].id == 0) {
			tr[k] = c;
			return;
		}
		int mid = (l + r) / 2;
		if (tr[k].val(mid) == c.val(mid)) {
			if (tr[k].id > c.id) swap(tr[k], c);
		}
		else if (tr[k].val(mid) < c.val(mid)) swap(tr[k], c);
		int fl = (c.val(l) < tr[k].val(l));
		int fr = (c.val(r) < tr[k].val(r));
		if (fl && fr) return;
		if (!fl) insert(LC, l, mid, a, mid, c);
		if (!fr) insert(RC, mid + 1, r, mid + 1, b, c);
		return;
	}
	int mid = (l + r) / 2;
	if (b <= mid) insert(LC, l, mid, a, b, c);
	else if (a > mid) insert(RC, mid + 1, r, a, b, c);
	else insert(LC, l, mid, a, mid, c), insert(RC, mid + 1, r, mid + 1, b, c);
}
line ask(int k, int l, int r, int a) {
	if (l == r) return tr[k];
	int mid = (l + r) / 2;
	line res;
	if (a <= mid) res = ask(LC, l, mid, a);
	else res = ask(RC, mid + 1, r, a);
	if (abs(res.val(a) - tr[k].val(a)) < eps) {
		if (res.id < tr[k].id) return res;
		else return tr[k];
	}
	else {
		if (res.val(a) > tr[k].val(a)) return res;
		else return tr[k];
	}
}
void clear(int k, int l, int r) {
	if (tr[k].id == 0) return;
	tr[k] = line(0, -INF, 0);
	if (l == r) return;
	int mid = (l + r) / 2;
	clear(LC, l, mid), clear(RC, mid + 1, r);
}
struct operation {
	int op, l, r;
	LL mn, cnt;
}ops[N];
int idx[N];
vector<int> f[N];
void work(int l, int r, int al, int ar) {
	if (l > r || al > ar) return;
	if (al == ar) {
		if (ops[al].op == 1) {
			repn(i, l, r) {
				int x = idx[i];
				if (a[x] + (LL)ops[al].cnt * x >= ops[al].mn) f[al].pb(x);
			}
		}
		return;
	}
	int mid = (al + ar) / 2;
	repn(i, al, mid) {
		if (ops[i].op == 1) insert(1, 1, n, 1, n, line(ops[i].cnt, -ops[i].mn, i));
	}
	vector<int> fl, fr;
	repn(i, l, r) {
		int x = idx[i];
		line lin = ask(1, 1, n, x);
		LL res = lin.val(x) + a[x];
		if (res >= 0) fl.pb(x);
		else fr.pb(x);
	}
	int t = l, md;
	for (auto x: fl) idx[t++] = x;
	md = t - 1;
	for (auto x: fr) idx[t++] = x;
	clear(1, 1, n);
	work(l, md, al, mid);
	work(md + 1, r, mid + 1, ar);
}
inline int lowbit(int x) {
	return x & -x;
}
LL v1[N], v2[N];
void insert(LL v[], int x, LL y) {
	for (int i = x; i <= n; i += lowbit(i)) v[i] += y;
}
LL get(LL v[], int x) {
	LL res = 0;
	for (int i = x; i; i -= lowbit(i)) res += v[i];
	return res;
}
int main() {
	IO;
	cin >> n >> m;
	rep(i, 1, M) tr[i].b = -INF;
	repn(i, 1, n) cin >> a[i], insert(v1, i, i), insert(v2, i, a[i]), idx[i] = i;
	build(1, 1, n);
	repn(i, 1, m) {
		int op, l, r;
		LL mn;
		cin >> op;
		if (op == 1) cin >> mn, ops[i] = {1, 0, 0, mn, cnt};
		else if (op == 2) cnt++, ops[i] = {2, 0, 0, 0, 0};
		else cin >> l >> r, ops[i] = {3, l, r, 0, 0};
	}
	work(1, n, 1, m);
	cnt = 0;
	repn(i, 1, m) {
		for (auto x: f[i]) {
			insert(v1, x, -x), insert(v2, x, -a[x]);
			a[x] = ops[i].mn;
			maintain(1, 1, n, x);
		}
		int op = ops[i].op;
		if (op == 1) change(1, 1, n, ops[i].mn);
		else if (op == 2) cnt++, apply_add(1, 1);
		else {
			int l = ops[i].l, r = ops[i].r;
			LL ans = get(v2, r) - get(v2, l - 1) + (get(v1, r) - get(v1, l - 1)) * cnt;
			ans += ask(1, 1, n, ops[i].l, ops[i].r);
			cout << ans << "\n";
		}
	}
	return 0;
}