#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e5 + 5;
const int MAXQ = 2e5 + 5;
const ll linf = 0x3f3f3f3f3f3f3f3f;

struct BIT
{
	ll tree[MAXN];
	int n;
	#define lowbit(x) ((x)&-(x))
	inline void update(int x,ll k)
	{
		while(x<=n)
			tree[x] += k,
			x += lowbit(x);
	}
	inline ll query(int x)
	{
		ll res = 0;
		while(x)
			res += tree[x],
			x ^= lowbit(x);
		return res;
	}
	inline ll query(int l,int r){ return query(r) - query(l-1);}
}tsum, tcoef;

struct Segment_Tree
{
	ll sum[MAXN<<2], coef[MAXN<<2];
	int cnt[MAXN<<2];
	pair<ll,int> mn[MAXN<<2], mx[MAXN<<2];
	ll tcov[MAXN<<2];
	int tadd[MAXN<<2];
	#define ls(u) ((u)<<1)
	#define rs(u) ((u)<<1|1)
	#define lson(u) ls(u),l,mid
	#define rson(u) rs(u),mid+1,r
	inline void push_up(int u)
	{
		sum[u] = sum[ls(u)] + sum[rs(u)];
		coef[u] = coef[ls(u)] + coef[rs(u)];
		cnt[u] = cnt[ls(u)] + cnt[rs(u)];
		mn[u] = mn[ls(u)].second? mn[ls(u)]: mn[rs(u)];
		mx[u] = mx[rs(u)].second? mx[rs(u)]: mx[ls(u)];
	}
	inline void upd_cov(int u,ll k)
	{
		if(!cnt[u]) return;
		sum[u] = cnt[u] * k;
		mn[u].first = mx[u].first = k;
		tcov[u] = k; tadd[u] = 0;
	}
	inline void upd_add(int u,int k)
	{
		sum[u] += coef[u] * k;
		mn[u].first += mn[u].second * k;
		mx[u].first += mx[u].second * k;
		tadd[u] += k;
	}
	inline void push_down(int u)
	{
		if(tcov[u] != -1)
		{
			upd_cov(ls(u), tcov[u]);
			upd_cov(rs(u), tcov[u]);
			tcov[u] = -1;
		}
		if(tadd[u])
		{
			upd_add(ls(u), tadd[u]);
			upd_add(rs(u), tadd[u]);
			tadd[u] = 0;
		}
	}
	void build(int u,int l,int r,bool flag)
	{
		tcov[u] = -1; tadd[u] = 0;
		if(l == r)
		{
			if(flag)
			{
				sum[u] = 0; coef[u] = l; cnt[u] = 1;
				mn[u] = mx[u] = {0, l};
			}
			else
			{
				sum[u] = coef[u] = cnt[u] = 0;
				mn[u] = {linf, 0}; mx[u] = {-linf, 0};
			}
			return;
		}
		int mid = (l+r)>>1;
		build(lson(u),flag); build(rson(u),flag);
		push_up(u);
	}
	void set(int u,int l,int r,int q,ll k)
	{
		if(l == r)
		{
			sum[u] = k; coef[u] = l; cnt[u] = 1;
			mn[u] = mx[u] = {k, l};
			return;
		}
		push_down(u);
		int mid = (l+r)>>1;
		if(q<=mid) set(lson(u),q,k);
		else set(rson(u),q,k);
		push_up(u);
	}
	void chk_min(int u,int l,int r,ll k)
	{
		if(mx[u].first <= k) return;
		if(mn[u].first > k){ upd_cov(u, k); return;}
		push_down(u);
		int mid = (l+r)>>1;
		chk_min(lson(u),k); chk_min(rson(u),k);
		push_up(u);
	}
	ll getsum(int u,int l,int r,int ql,int qr)
	{
		if(ql<=l && r<=qr) return sum[u];
		push_down(u);
		int mid = (l+r)>>1;
		ll res = 0;
		if(ql<=mid) res += getsum(lson(u),ql,qr);
		if(mid<qr) res += getsum(rson(u),ql,qr);
		return res;
	}
	
	int n;
	void build(int _n,bool flag){ n = _n; build(1,1,n,flag);}
	void set(int q,ll k){ set(1,1,n,q,k);}
	void chk_min(ll k){ chk_min(1,1,n,k);}
	ll getsum(int ql,int qr){ return getsum(1,1,n,ql,qr);}
}tree;

struct Oper
{
	int type, l, r;
	ll v;
	void read_self(void)
	{
		scanf("%d",&type);
		if(type == 1) scanf("%lld",&v);
		else if(type == 3) scanf("%d%d",&l,&r);
	}
}op[MAXQ];

ll a[MAXN];

int main(void)
{
	int n,Q;
	scanf("%d%d",&n,&Q);
	for(int i=1; i<=n; ++i) scanf("%lld",&a[i]);
	for(int i=1; i<=Q; ++i) op[i].read_self();
	
	static vector<int> eff[MAXQ];
	
	int tot = 0;
	for(int i=1; i<=Q; ++i)
		tot += op[i].type == 1;
	
	vector< tuple<int,int,int> > pt(n); // {l, r, id}
	for(int i=1; i<=n; ++i)
		pt[i-1] = make_tuple(0, tot, i);
	if(tot == 0) pt.clear();
	while(pt.size())
	{
		decltype(pt) nxt;
		vector<int> curmid(pt.size());
		for(int i=0; i<(int)pt.size(); ++i)
			curmid[i] = (get<0>(pt[i]) + get<1>(pt[i]) + 1) / 2;
		
		const ll LIM = 1.1e12;
		tree.build(n, 1);
		tree.upd_cov(1, LIM);
		for(int i=1, j=0, has1=0, has2=0; i<=Q; ++i)
		{
			if(op[i].type == 2) ++has2, tree.upd_add(1, 1);
			if(op[i].type != 1) continue;
			tree.chk_min(op[i].v);
			++has1;
			for(; j<(int)pt.size() && curmid[j]<=has1; ++j)
			{
				int l, r, id, mid = curmid[j];
				tie(l, r, id) = pt[j];
				if(tree.getsum(id,id) < a[id] + (ll)id * has2)
					r = mid - 1;
				else
					l = mid;
				
				if(l == r) eff[l+1].emplace_back(id);
				else nxt.emplace_back(l, r, id);
			}
		}
		sort(nxt.begin(), nxt.end(), [&] (const tuple<int,int,int> &x,const tuple<int,int,int> &y){
			return get<0>(x) < get<0>(y);
		});
		pt.swap(nxt);
	}
	
	tree.build(n,0);
	tsum.n = tcoef.n = n;
	for(int i=1; i<=n; ++i)
	{
		tsum.update(i, a[i]);
		tcoef.update(i, i);
	}
	
	int has1 = 0, has2 = 0;
	for(int i=1; i<=Q; ++i)
	{
		if(op[i].type == 1)
		{
			++has1;
			ll v = op[i].v;
			tree.chk_min(v);
			for(int j: eff[has1])
			{
				tsum.update(j, -a[j]);
				tcoef.update(j, -j);
				tree.set(j, v);
			}
		}
		else if(op[i].type == 2)
		{
			++has2;
			tree.upd_add(1, 1);
		}
		else
		{
			int l = op[i].l, r = op[i].r;
			ll ans = tree.getsum(l,r);
			ans += tsum.query(l,r) + has2 * tcoef.query(l,r);
			printf("%lld\n",ans);
		}
	}
	return 0;
}