#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5, blk = 1250;
int n, m, lt[maxn], rt[maxn], bel[maxn], cov[maxn];
long long sum[maxn], add[maxn], a[maxn];
bitset<maxn> bt[405];
void re(int x)
{
	sum[x] = 0;
	if (~cov[x]) for (int j = lt[x]; j <= rt[x]; j++) a[j] = cov[x];
	cov[x] = -1;
	bt[x].reset();
	for (int j = lt[x]; j <= rt[x]; j++)
	{
		a[j] += add[x], sum[x] += a[j];
		if (a[j] < n) bt[x].set(a[j]);
	}
	add[x] = 0;
}
bool check(int x, int l, int r)
{
	int il = bel[l], ir = bel[r];
	for (int i = l; i <= min(r, rt[il]); i++)
	{
		int tmp = a[i];
		if (~cov[il]) tmp = cov[il];
		tmp += add[il];
		if (tmp == x) return 1;
	}
	if (il != ir)
		for (int i = lt[ir]; i <= r; i++)
		{
			int tmp = a[i];
			if (~cov[ir]) tmp = cov[ir];
			tmp += add[ir];
			if (tmp == x) return 1;
		}
	for (int i = il + 1; i < ir; i++)
	{
		if (~cov[i])
		{
			if (x == add[i] + cov[i]) return 1;
		}
		else if (x >= add[i] && bt[i][x - add[i]]) return 1;
	}
	return 0;
}
signed main()
{
//	freopen("1.in", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    memset(cov, -1, sizeof(cov));
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i += blk)
    {
    	int l = i, r = min(n, i + blk - 1), id = (i - 1) / blk + 1;
    	lt[id] = l, rt[id] = r;
    	for (int j = l; j <= r; j++)
    	{
    		if (a[j] < n) bt[id].set(a[j]);
			bel[j] = id;
		}
	}
	while (m--)
	{
		int op, l, r, v;
		cin >> op >> l >> r;
		int il = bel[l], ir = bel[r];
		if (op == 1)
		{
			cin >> v;
			if (il == ir)
			{
				sum[il] = 0;
				for (int i = lt[il]; i <= rt[il]; i++)
					a[i] = (cov[il] == -1 ? a[i] : cov[il]) + add[il], sum[il] += a[i];
				cov[il] = -1, add[il] = 0;
				for (int i = l; i <= r; i++) a[i] = v;
				re(il);
				continue;
			}
			for (int i = il + 1; i < ir; i++)
			{
				cov[i] = v, add[i] = 0;
				sum[i] = 1ll * v * (rt[i] - lt[i] + 1);
			}
			for (int i = lt[il]; i <= rt[il]; i++)
				a[i] = (cov[il] == -1 ? a[i] : cov[il]) + add[il];
			for (int i = lt[ir]; i <= rt[ir]; i++)
				a[i] = (cov[ir] == -1 ? a[i] : cov[ir]) + add[ir];
			cov[il] = cov[ir] = -1, add[il] = add[ir] = 0;
			for (int i = l; i <= rt[il]; i++) a[i] = v;
			for (int i = lt[ir]; i <= r; i++) a[i] = v;
			re(il), re(ir);
		}
		else if (op == 2)
		{
			int i;
			for (i = 0; check(i, l, r); i++);
			if (~cov[il])
			{
				for (int j = lt[il]; j <= rt[il]; j++)
					a[j] = cov[il];
				cov[il] = -1;
			}
			if (~cov[ir])
			{
				for (int j = lt[ir]; j <= rt[ir]; j++)
					a[j] = cov[ir];
				cov[ir] = -1;
			}
			for (int j = l; j <= min(r, rt[il]); j++)
				a[j] += i;
			re(il);
			if (il != ir)
			{
				for (int j = lt[ir]; j <= r; j++)
					a[j] += i;
				re(ir);
			}
			for (int j = il + 1; j < ir; j++)
				add[j] += i, sum[j] += 1ll * i * (rt[j] - lt[j] + 1);
		}
		else
		{
			long long ans = 0;
			for (int i = il + 1; i < ir; i++)
				ans += sum[i];
			for (int i = l; i <= min(r, rt[il]); i++)
			{
				if (~cov[il]) ans += cov[il] + add[il];
				else ans += a[i] + add[il];
			}
			if (il != ir)
				for (int i = lt[ir]; i <= r; i++)
				{
					if (~cov[ir]) ans += cov[ir] + add[ir];
					else ans += a[i] + add[ir];
				}
			cout << ans << '\n';
		}
	}
    return 0;
}
/*
5 6
0 7 2 1 0
1 2 4 0
2 1 3
2 3 4
1 2 3 4
2 1 5
3 2 5
1 4 4 2 0
*/