// #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 = 700;
int T, N, M, K;

struct Block {
	int addTag, coverTag = -1;
	int vis[MaxN];
	ll sum;

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

	void rebuild() {
		if (coverTag != -1) {
			for (int i = 0; i < MaxN; i++) {
				vis[i] = 0;
			}
			vis[coverTag] = a.size();

			for (auto &x : a) x = coverTag;

			coverTag = -1;
		}

		if (addTag) {
			for (auto &x : a) {
				vis[x]--;
				x += addTag;
				vis[x]++;
			}

			addTag = 0;
		}

	}
	void cover(int v) {
		coverTag = v;
		addTag = 0;
		sum = a.size() * coverTag;
	}
	void cover(int i, int v) {
		vis[a[i]]--;
		sum -= a[i];

		a[i] = v;

		sum += a[i];
		vis[a[i]]++;
	}

	void add(int i, int v) {
		vis[a[i]]--;
		sum -= a[i];

		a[i] += v;

		sum += a[i];
		vis[a[i]]++;
	}
	void add(int v) {
		addTag += v;
		sum += addTag * a.size();
	}

	bool query(int i, int v) {
		if (coverTag != -1) {
			return coverTag + addTag == v;
		} else {
			return a[i] + addTag == v;
		}
	}

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

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

	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) {
	int ans = 0;
	for (int i = l; i <= r;) {
		if (i % SIZ == 0 && i + SIZ <= r + 1) {
			ans += block[i / SIZ].query(v);
			i += SIZ;
		} else {
			ans += block[i / SIZ].query(i % SIZ, v);
			i++;
		}
		if (ans > 0) return true;
	}
	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--;
		block[l / SIZ].rebuild();
		block[r / SIZ].rebuild();
		if (opt == 1) {
			int v;
			cin >> v;
			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;
		}
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	srand(time(NULL));
#ifdef MULTI_CASES
	int T;
	cin >> T;
	while (T--)
#endif
		Solve();
}