#include<bits/stdc++.h>
#define lc (rt << 1)
#define rc (rt << 1) | 1
using namespace std;
const int MAXN = 200005;
typedef long long LL;
const int B = 450;
const LL INF = 0x3f3f3f3f3f3f3f3f;

int n, q, tot, vis[MAXN], type[MAXN], ql[MAXN], qr[MAXN];
LL a[MAXN], qv[MAXN];
vector<int> ins[MAXN];

struct Line {
	int id;
	LL k, b;
	inline LL val(LL x) {
		return k * x + b;
	}
} line[MAXN], stk[MAXN];
int top;

inline bool Check(Line a, Line b, Line c) {
	return ((a.b - c.b) * (b.k - a.k) <= (a.b - b.b) * (c.k - a.k));
}

struct BIT {
	LL tr[MAXN];
	void add(int x, LL v) {
		for (; x <= n; x += (x & (-x))) {
			tr[x] += v;
		}
	}
	LL sum(int x) {
		LL ret = 0;
		for (; x; x -= (x & (-x))) {
			ret += tr[x];
		}
		return ret;
	}
	LL qry(int l, int r) {
		return sum(r) - sum(l - 1);
	}
} bit1, bit2;

struct Node {
	int mx;
	LL icnt, isum, vsum, itsum;
};

struct SegmentTree {
	LL vtag[MAXN << 2], ttag[MAXN << 2];
	Node seg[MAXN << 2];

	inline Node Merge(Node x, Node y) {
		Node z;
		z.mx = max(x.mx, y.mx);
		z.icnt = x.icnt + y.icnt;
		z.isum = x.isum + y.isum;
		z.vsum = x.vsum + y.vsum;
		z.itsum = x.itsum + y.itsum;
		return z;
	}

	inline void puttag(int rt, LL vtg, LL ttg) {
		vtag[rt] = vtg;
		ttag[rt] = ttg;
		seg[rt].vsum = seg[rt].icnt * vtg;
		seg[rt].itsum = seg[rt].isum * ttg;
	}

	inline void pushdown(int rt) {
		if (vtag[rt] && ttag[rt]) {
			puttag(lc, vtag[rt], ttag[rt]);
			puttag(rc, vtag[rt], ttag[rt]);
			vtag[rt] = ttag[rt] = 0;
		}
	}

	void Insert(int rt, int b, int e, int p, LL v, LL t) {
		if (b == e) {
			seg[rt].mx = p;
			seg[rt].icnt = 1;
			seg[rt].isum = p;
			seg[rt].vsum = v;
			seg[rt].itsum = t * p;
			return;
		}
		int mid = (b + e) >> 1;
		pushdown(rt);
		if (p <= mid) Insert(lc, b, mid, p, v, t);
		else Insert(rc, mid + 1, e, p, v, t);
		seg[rt] = Merge(seg[lc], seg[rc]);
	}

	void Cover(int rt, int b, int e, int l, int r, LL v, LL t) {
		if (l <= b && e <= r) {
			puttag(rt, v, t);
			return;
		}
		int mid = (b + e) >> 1;
		pushdown(rt);
		if (l <= mid) Cover(lc, b, mid, l, r, v, t);
		if (r > mid) Cover(rc, mid + 1, e, l, r, v, t);
		seg[rt] = Merge(seg[lc], seg[rc]);
	}

	LL Ask(int rt, int b, int e, int p) {
		if (b == e) {
			if (!seg[rt].icnt) return INF; 
			return seg[rt].vsum - seg[rt].itsum;
		}
		int mid = (b + e) >> 1;
		pushdown(rt);
		if (seg[lc].mx >= p) return Ask(lc, b, mid, p);
		else return Ask(rc, mid + 1, e, p);
	}

	Node Query(int rt, int b, int e, int l, int r) {
		if (l <= b && e <= r) return seg[rt];
		int mid = (b + e) >> 1;
		pushdown(rt);
		if (r <= mid) return Query(lc, b, mid, l, r);
		if (l > mid) return Query(rc, mid + 1, e, l, r);
		return Merge(Query(lc, b, mid, l, r), Query(rc, mid + 1, e, l, r));
	}
} segt;

void solve() {
	scanf("%d %d", &n, &q);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
		bit1.add(i, a[i]);
		bit2.add(i, i);
	}
	for (int i = 1, addcnt = 0; i <= q; ++i) {
		scanf("%d", &type[i]);
		if (type[i] == 1) {
			scanf("%lld", &qv[i]);
			line[++tot] = (Line){i, -addcnt, qv[i]};
		} else if (type[i] == 2) {
			++addcnt;
		} else if (type[i] == 3) {
			scanf("%d %d", &ql[i], &qr[i]);
		}
	}

	for (int l = 1, r; l <= tot; l = r + 1) {
		r = min(tot, l + B - 1);
		for (int j = l; j <= r; ++j) {
			if (top && stk[top].k == line[j].k) {
				if (stk[top].b > line[j].b) {
					--top;
				} else {
					continue;
				}
			}
			while (top > 1 && Check(stk[top - 1], stk[top], line[j])) {
				--top;
			}
			stk[++top] = line[j];
		}
		for (int i = 1, ptr = 1; i <= n; ++i) {
			if (vis[i]) continue;
			while (ptr < top && stk[ptr].val(i) >= stk[ptr + 1].val(i)) {
				++ptr;
			}
			if (stk[ptr].val(i) <= a[i]) {
				vis[i] = 1;
				for (int j = l; j <= r; ++j) {
					if (line[j].val(i) <= a[i]) {
						//cerr << "wow " << i << ' ' << line[j].id << endl;
						ins[line[j].id].push_back(i);
						break;
					}
				}
			}
		}
	}

	for (int i = 1, addcnt = 0; i <= q; ++i) {
		if (type[i] == 1) {
			LL v = qv[i];
			int L = 1, R = n, pos = n + 1;
			while (L <= R) {
				int mid = (L + R) >> 1;
				if (segt.Ask(1, 1, n, mid) + 1LL * mid *  addcnt >= v) {
					pos = mid;
					R = mid - 1;
				} else {
					L = mid + 1;
				}
			}
			if (pos <= n) {
				segt.Cover(1, 1, n, pos, n, v, addcnt);
			}
			for (auto j : ins[i]) {
				segt.Insert(1, 1, n, j, v, addcnt);
				bit1.add(j, -a[j]);
				bit2.add(j, -j);
			}
		} else if (type[i] == 2) {
			++addcnt;
		} else if (type[i] == 3) {
			int l = ql[i], r = qr[i];
			LL ans = bit1.qry(l, r);
			ans += bit2.qry(l, r) * addcnt;
			Node cur = segt.Query(1, 1, n, l, r);
			//cerr << cur.vsum << ' ' << cur.isum << ' ' << cur.itsum << endl;
			ans += cur.vsum;
			ans += cur.isum * addcnt - cur.itsum;
			printf("%lld\n", ans);
		}
	}
}

int main() {
	solve();
	return 0;
}