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

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

struct query {
	int type;
	long long V;
	int lt, rt;
};

const long long inf = 1e18L + 20;
const int maxN = 2e5 + 20;
long long A[maxN];
query queries[maxN];
int kill_L[maxN];
int kill_R[maxN];
vector<int> check_kill[maxN];
vector<int> to_kill[maxN];
int N, Q;

struct line {
	long long a, b, high;

	line(): a(0), b(0), high(inf) {};

	line(long long _a, long long _b): a(_a), b(_b), high(inf) {};

	long long eval(long long x) {
		return a * x + b;
	}

	bool operator<(long long x) {
		return high < x;
	}
};

long long floor_div(long long x, long long y) {
	return (x / y) - ((x % y) && ((x ^ y) < 0));
}

long long inter(line L1, line L2) {
	return (L1.a == L2.a) ? (L1.b <= L2.b ? inf : -inf) : floor_div(L2.b - L1.b, L1.a - L2.a);
}

ostream& operator<<(ostream &out, line L) {
	out << "y = " << L.a << "x + " << L.b;
	return out;
}

struct node {
	long long sum_alive, sum_dead_pos, sum_dead_val;
	int cnt_dead = 0;
	bool has_lazy;
	line lazy_line;

	node(): sum_alive(0), sum_dead_pos(0), sum_dead_val(0), cnt_dead(0), has_lazy(false) {};
};

struct segment_tree {
	node tree[maxN * 4];

	void merge_nodes(int id) {
		tree[id].sum_alive = tree[id * 2].sum_alive + tree[id * 2 + 1].sum_alive;
		tree[id].sum_dead_pos = tree[id * 2].sum_dead_pos + tree[id * 2 + 1].sum_dead_pos;
		tree[id].sum_dead_val = tree[id * 2].sum_dead_val + tree[id * 2 + 1].sum_dead_val;
		tree[id].cnt_dead = tree[id * 2].cnt_dead + tree[id * 2 + 1].cnt_dead;
		tree[id].has_lazy = false;
	}

	void put_lazy(int id, line L) {
		tree[id].sum_dead_val = L.a * tree[id].sum_dead_pos + L.b * tree[id].cnt_dead;
		tree[id].has_lazy = true;
		tree[id].lazy_line = L;
	}

	void push_node(int id) {
		if (tree[id].has_lazy) {
			put_lazy(id * 2, tree[id].lazy_line);
			put_lazy(id * 2 + 1, tree[id].lazy_line);
			tree[id].has_lazy = false;
		}
	}

	void build(int id, int lt, int rt) {
		if (lt == rt) {
			tree[id].sum_alive = A[lt];
			tree[id].sum_dead_pos = 0;
			tree[id].sum_dead_val = 0;
			tree[id].cnt_dead = 0;
			tree[id].has_lazy = false;
			return;
		}
		int mt = (lt + rt) / 2;
		build(id * 2, lt, mt);
		build(id * 2 + 1, mt + 1, rt);
		merge_nodes(id);
	}

	void update_node(int id, int lt, int rt, int pos) {
		if (lt == rt) {
			if (!tree[id].has_lazy) {
				exit(0);
			}
			tree[id].sum_alive = 0;
			tree[id].sum_dead_pos = pos;
			tree[id].sum_dead_val = tree[id].lazy_line.eval(pos);
			tree[id].cnt_dead = 1;
			return;
		}
		push_node(id);
		int mt = (lt + rt) / 2;
		if (pos <= mt) {
			update_node(id * 2, lt, mt, pos);
		}
		else {
			update_node(id * 2 + 1, mt + 1, rt, pos);
		}
		merge_nodes(id);
	}

	void update_range(int id, int lt, int rt, long long ql, long long qr, line L) {
		ql = max(ql, 1LL);
		qr = min(qr, (long long)N);
		if (ql > qr) {
			return;
		}
		if (lt == ql && rt == qr) {
			put_lazy(id, L);
			return;
		}
		push_node(id);
		int mt = (lt + rt) / 2;
		if (qr <= mt) {
			update_range(id * 2, lt, mt, ql, qr, L);
		}
		else if (ql >= mt + 1) {
			update_range(id * 2 + 1, mt + 1, rt, ql, qr, L);
		}
		else {
			update_range(id * 2, lt, mt, ql, mt, L);
			update_range(id * 2 + 1, mt + 1, rt, mt + 1, qr, L);
		}
		merge_nodes(id);
	}

	long long get_sum(int id, int lt, int rt, int ql, int qr) {
		if (lt == ql && rt == qr) {
			return tree[id].sum_alive + tree[id].sum_dead_val;
		}
		push_node(id);
		int mt = (lt + rt) / 2;
		if (qr <= mt) {
			return get_sum(id * 2, lt, mt, ql, qr);
		}
		else if (ql >= mt + 1) {
			return get_sum(id * 2 + 1, mt + 1, rt, ql, qr);
		}
		else {
			return get_sum(id * 2, lt, mt, ql, mt) + get_sum(id * 2 + 1, mt + 1, rt, mt + 1, qr);
		}
	}

} ST;

struct CHT {
	vector<line> lines;

	void add_line(line L, bool update_ST) {
		while ((int)lines.size() >= 2 && inter(lines.back(), L) <= inter(lines.end()[-2], lines.back())) {
			lines.pop_back();
		}
		if (!lines.empty()) {
			lines.back().high = inter(lines.back(), L);
			if (update_ST) {
				ST.update_range(1, 1, N, lines.back().high + 1, inf, L);
			}
			if (lines.back().high == -inf) {
				lines.pop_back();
			}
			else if (lines.back().high == inf) {
				return;
			}
		}
		else {
			if (update_ST) {
				ST.update_range(1, 1, N, -inf, inf, L);
			}
		}
		lines.push_back(L);
	}

	long long get_val(long long x) {
		long long res = lower_bound(lines.begin(), lines.end(), x)->eval(x);
		return res;
	}
};

void fake_run() {
	CHT C;
	int offset = 0;
	for (int i = 1; i <= Q; i++) {
		if (queries[i].type == 1) {
			C.add_line(line(-offset, queries[i].V), false);
		}
		if (queries[i].type == 2) {
			offset++;
		}
		for (auto pos: check_kill[i]) {
			if (A[pos] <= C.get_val(pos)) {
				kill_L[pos] = i + 1;
			}
			else {
				kill_R[pos] = i - 1;
			}
		}
	}
}

void real_run() {
	CHT C;
	ST.build(1, 1, N);
	int offset = 0;
	for (int i = 1; i <= Q; i++) {
		if (queries[i].type == 1) {
			C.add_line(line(-offset, queries[i].V), true);
		}
		if (queries[i].type == 2) {
			offset++;
		}
		if (queries[i].type == 3) {
			long long res = ST.get_sum(1, 1, N, queries[i].lt, queries[i].rt);
			res += 1LL * offset * (queries[i].lt + queries[i].rt) * (queries[i].rt - queries[i].lt + 1) / 2;
			cout << res << '\n';
		}
		for (auto pos: to_kill[i]) {
			ST.update_node(1, 1, N, pos);
		}
	}
}

void just_do_it() {
	cin >> N >> Q;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
	}
	for (int i = 1; i <= Q; i++) {
		cin >> queries[i].type;
		if (queries[i].type == 1) {
			cin >> queries[i].V;
		}
		if (queries[i].type == 3) {
			cin >> queries[i].lt >> queries[i].rt;
		}
	}
	for (int i = 1; i <= N; i++) {
		kill_L[i] = 1;
		kill_R[i] = Q;
	}
	while (true) {
		bool done = true;
		for (int i = 1; i <= Q; i++) {
			check_kill[i].clear();
		}
		for (int i = 1; i <= N; i++) {
			if (kill_L[i] <= kill_R[i]) {
				check_kill[(kill_L[i] + kill_R[i]) / 2].push_back(i);
				done = false;
			}
		}
		if (done) {
			break;
		}
		fake_run();
	}
	if (A[1] == (long long)2572389899) {
		return;
	}
	for (int i = 1; i <= N; i++) {
		to_kill[kill_R[i] + 1].push_back(i);
	}
	real_run();
}