#pragma GCC optimize(1, 2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
// #define int ll
#define ls p << 1
#define rs p << 1 | 1
#define lowbit(x) ((x) & (-x))
#define endl '\n'
#define ld long double

using PII = pair<int, int>;
using vi = vector<int>;
using t3i = tuple<int, int, int>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// #define MULTI_CASES
const int MaxN =  5e5 + 10;
const int INF = 1e9;
const int SIZ = 1000;
int T, N, M, K;

struct Block {
	int addTag, coverTag = -1;
	bitset<MaxN> vis;
	ll sum;

	vi a;
	void addOne(int v) {
		a.emplace_back(v);
		sum += v;
        vis.set(v);
	}

	bool get(int v) {
		if (v < 0 || v >= MaxN) return 0;
		return vis[v];
	}

	void rebuild() {
        vis.reset();
		if (coverTag != -1) {	
			for (auto &x : a) {
				x = coverTag;
			}
			coverTag = -1;
		}
        sum = 0;
        if (addTag) {
            for (auto &x : a) {
                x += addTag;
                sum += x;
                if (x < MaxN) vis.set(x);
            }
            addTag = 0;
        }
	}
    void reCover() {
		if (coverTag != -1) {	
			for (auto &x : a) {
				x = coverTag + addTag;
			}
			coverTag = -1;
            addTag = 0;
		}
    }
	void cover(int v) {
		coverTag = v;
		addTag = 0;
		sum = a.size() * coverTag;
	}
	void add(int v) {
		addTag += v;
		sum += v * a.size();
	}
	void cover(int i, int v) {
        sum += v - addTag - a[i];
		a[i] = v - addTag;
	}
	void add(int i, int v) {
		a[i] += v;
        sum += v;
	}
	bool query(int i, int v) {
		if (coverTag != -1) {
			return coverTag + addTag == v;
		} else {
			return a[i] + addTag == v;
		}
	}

	bool query(int v) {
		if (coverTag != -1) {
			return coverTag + addTag == v;
		} else {
			return get(v - addTag);
		}
	}

	ll getSum() {
		return sum;
	}

	ll getSum(int i) {
		if (coverTag != -1) {
			return coverTag + addTag;
		} else {
			return a[i] + addTag;
		}
	}
} block[MaxN / SIZ + 1];

bool getAns(int l, int r, int v) {
	for (int i = l; i <= r;) {
		if (i % SIZ == 0 && i + SIZ <= r + 1) {
			if (block[i / SIZ].query(v)) return true;
			i += SIZ;
		} else {
			if (block[i / SIZ].query(i % SIZ, v)) return true;
			i++;
		}
	}
	return false;
}

inline void Solve() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		block[i / SIZ].addOne(x);
	}

	while (M--) {
		int opt, l, r;
		cin >> opt >> l >> r;
		l--, r--;
		
		if (opt == 1) {
			int v;
			cin >> v;
            block[l / SIZ].reCover();
		    block[r / SIZ].reCover();
			for (int i = l; i <= r;) {
				if (i % SIZ == 0 && i + SIZ <= r + 1) {
					block[i / SIZ].cover(v);
					i += SIZ;
				} else {
					block[i / SIZ].cover(i % SIZ, v);
					i++;
				}
			}
		} else if (opt == 2) {
			int ans = 0;
			while (ans <= N && getAns(l, r, ans)) {
				ans++;
			}

			// cerr << ans << endl;

			for (int i = l; i <= r;) {
				if (i % SIZ == 0 && i + SIZ <= r + 1) {
					block[i / SIZ].add(ans);
					i += SIZ;
				} else {
					block[i / SIZ].add(i % SIZ, ans);
					i++;
				}
			}
		} else {
			ll ans = 0;
			for (int i = l; i <= r;) {
				if (i % SIZ == 0 && i + SIZ <= r + 1) {
					ans += block[i / SIZ].getSum();
					i += SIZ;
				} else {
					ans += block[i / SIZ].getSum(i % SIZ);
					i++;
				}
			}
			cout << ans << endl;
		}
		block[l / SIZ].rebuild();
		block[r / SIZ].rebuild();
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef MULTI_CASES
	int T;
	cin >> T;
	while (T--)
#endif
		Solve();
}