#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5, blk = 400;
int n, m, a[maxn], add[maxn], lt[maxn], rt[maxn], bel[maxn], cov[maxn];
long long sum[maxn];
bitset<maxn> bt[2005];
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 (bt[i][x]) return 1;
	return 0;
}
signed main()
{
    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)
		{
			if (n >= 100) continue;
			cin >> v;
			if (il == ir)
			{
				for (int i = lt[il]; i <= rt[il]; i++)
					a[i] = (cov[il] == -1 ? a[i] : cov[il]) + add[il];
				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, bt[i].reset();
				if (v < n) bt[i].set(v);
				sum[i] = 1ll * v * (rt[i] - lt[i] + 1);
			}
			for (int i = lt[il]; i <= rt[il]; i++) a[i] = cov[il];
			for (int i = lt[il]; i <= rt[il]; i++) a[i] += add[il];
			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;
			sum[il] = sum[ir] = 0;
			for (int i = lt[il]; i <= rt[il]; i++) sum[il] += a[i];
			sum[il] = sum[ir] = 0;
			for (int i = lt[ir]; i <= rt[ir]; i++) sum[ir] += a[i];
			re(il), re(ir);
		}
		else if (op == 2)
		{
//			if (n >= 100) continue;
			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, sum[j] += i;
			re(il);
			if (il != ir)
			{
				for (int j = lt[ir]; j <= r; j++)
					a[j] += i, sum[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
		{
//			if (n >= 100) continue;
			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 8
0 7 2 1 0
1 2 4 0
2 1 3
2 3 4
3 1 3
1 2 3 4
3 1 4
2 1 5
3 2 5
*/