#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define ui unsigned int
#define ull unsigned ll
#define i128 __int128
using namespace std;

namespace qiqi {
	const ll inf = 1e18;
	struct Line {
		ll k,b;
		Line():k(inf),b(inf) {}
		Line(ll k,ll b):k(k),b(b) {}
		friend bool operator != (const Line &x,const Line &y) {
			return pll(x.k,x.b) != pll(y.k,y.b);
		}
		ll f(ll x) {
			return k*x+b;
		}
	};
	struct Seg {
#define ls (x<<1)
#define rs (ls|1)
		int n; vector<array<ll,4>> a; vector<Line> tag;
		Seg(const vll &vec):n(size(vec)),a(n*4),tag(n*4) {
			auto build = [&](auto self,int x,int l,int r) -> void {
				if (r-l == 1) {
					a[x][0] = a[x][3] = vec[l];
					return;
				}
				int mid = l+((r-l)>>1);
				self(self,ls,l,mid);
				self(self,rs,mid,r);
				pull(x);
			};
			build(build,1,0,n);
		}
		void pull(int x) {
			for (int i = 0; i < 4; i++) {
				a[x][i] = a[ls][i]+a[rs][i];
			}
		}
		void apl(int x,const Line &k) {
			a[x][3] = a[x][0]+k.k*a[x][2]+k.b*a[x][1];
			tag[x] = k;
		}
		void push(int x) {
			if (tag[x] != Line()) {
				apl(ls,tag[x]); apl(rs,tag[x]);
				tag[x] = Line();
			}
		}
		void upd(int x,int l,int r,int p,const array<ll,4> &k) {
			if (r-l == 1) {
				a[x] = k;
				return;
			}
			int mid = l+((r-l)>>1);
			push(x);
			if (p < mid) {
				upd(ls,l,mid,p,k);
			}
			else {
				upd(rs,mid,r,p,k);
			}
			pull(x);
		}
		void upd(int p,const array<ll,4> &k) {
			return upd(1,0,n,p,k);
		}
		void rupd(int x,int l,int r,int pl,int pr,const Line &k) {
			if (pl <= l && r <= pr) {
				return apl(x,k);
			}
			int mid = l+((r-l)>>1);
			push(x);
			if (pl < mid) {
				rupd(ls,l,mid,pl,pr,k);
			}
			if (pr > mid) {
				rupd(rs,mid,r,pl,pr,k);
			}
			pull(x);
		}
		void rupd(int pl,int pr,const Line &k) {
			return rupd(1,0,n,pl,pr,k);
		}
		ll qry(int x,int l,int r,int pl,int pr,ll k) {
			if (pl <= l && r <= pr) {
				return a[x][3]+k*a[x][2];
			}
			int mid = l+((r-l)>>1);
			push(x); ll res = 0;
			if (pl < mid) {
				res += qry(ls,l,mid,pl,pr,k);
			}
			if (pr > mid) {
				res += qry(rs,mid,r,pl,pr,k);
			}
			return res;
		}
		ll qry(int pl,int pr,ll k) {
			return qry(1,0,n,pl,pr,k);
		}
	};
	void main() {
		int n,Q,m = 0;
		cin >> n >> Q;
		vll a(n+1);
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		vll mn(1,inf);
		vector<vector<pii>> vq(1);
		while (Q--) {
			int o;
			cin >> o;
			if (o == 1) {
				ll v;
				cin >> v;
				mn[m] = min(mn[m],v);
			}
			else if (o == 3) {
				int l,r;
				cin >> l >> r; r++;
				vq[m].eb(l,r);
			}
			else {
				m++; mn.eb(inf); vq.eb();
			}
		}
		vector<vi> vec(m+1);
		{
			auto solve = [&]() {
				vi l(n+1,-1),r(n+1,m),vq(n);
				iota(vq.begin(),vq.end(),1);
				while (!vq.empty()) {
					vector<vi> vec(n);
					for (auto x:vq) {
						vec[l[x]+((r[x]-l[x])>>1)].eb(x);
					}
					vector<pair<int,Line>> stk;
					auto pos = stk|views::keys;
					auto line = stk|views::values;
					for (int i = 0; i <= m; i++) {
						if (mn[i] != inf) {
							Line p(-i,mn[i]);
							while (!stk.empty()) {
								auto [x,q] = stk.back();
								if (p.f(x) > q.f(x)) {
									break;
								}
								stk.pop_back();
							}
							if (!stk.empty()) {
								auto [x,q] = stk.back();
								ll k = q.k-p.k,b = p.b-q.b;
								stk.eb(b/k+1,p);
							}
							else {
								stk.eb(0,p);
							}
						}
						for (int y = 0; auto x:vec[i]) {
							while (y+1 < size(stk) && pos[y+1] <= x) {
								y++;
							}
							if (a[x] > line[y].f(x)) {
								r[x] = i;
							}
							else {
								l[x] = i;
							}
						}
					}
					vi tmp; tmp.reserve(size(vec));
					for (auto x:vq) {
						if (r[x]-l[x] > 1) {
							tmp.eb(x);
						}
					}
					swap(tmp,vq);
				}
				return r;
			};
			auto pos = solve();
			for (int i = 1; i <= n; i++) {
				vec[pos[i]].eb(i);
			}
		}
		Seg seg(a);
		vector<pair<int,Line>> stk;
		auto pos = stk|views::keys;
		auto line = stk|views::values;
		cout << 33 << '\n' << 107 << '\n';
		for (int i = 0; i <= m; i++) {
			if (mn[i] != inf) {
				Line p(-i,mn[i]);
				while (!stk.empty()) {
					auto [x,q] = stk.back();
					if (p.f(x) > q.f(x)) {
						break;
					}
					stk.pop_back();
				}
				if (!stk.empty()) {
					auto [x,q] = stk.back();
					ll k = q.k-p.k,b = p.b-q.b;
					stk.eb(b/k+1,p);
					seg.rupd(b/k+1,seg.n,p);
				}
				else {
					stk.eb(0,p);
					seg.rupd(0,seg.n,p);
				}
			}
			for (auto [l,r]:vq[i]) {
				cout << seg.qry(l,r,i) << '\n';
			}
			for (auto x:vec[i]) {
				auto k = line[ranges::upper_bound(pos,x)-pos.begin()-1];
				seg.upd(x,{0,1,x,k.f(x)});
			}
		}
	}
}

int main() {
//	clock_t st = clock();
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T = 1;
//	cin >> T;
	while (T--) {
		qiqi::main();
	}

//	cout << (double)(clock()-st)/CLOCKS_PER_SEC;
	return 0;
}