#include <bits/stdc++.h>
#define X first
#define Y second
#define PB push_back
#define x first
#define y second
#define pb push_back
#define all(a) begin(a),end(a)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
using pii=pair<int,int>;

const int N = 5e5 + 500;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const char en='\n';
const ll LLINF=1ll<<60;
const int K = 500;
const int OFF = (1 << 19);

int n;

bitset < K > T_msk[2 * OFF];
ll T_sum[2 * OFF], prop_add[2 * OFF], prop_set[2 * OFF];

void refresh(int x, int len) {
	if(prop_set[x] != -1) {
		T_msk[x].reset();
		if(prop_set[x] < K)
			T_msk[x][prop_set[x]] = 1;
		T_sum[x] = (ll)len * prop_set[x];
		if(x < OFF) {
			prop_set[2 * x] = prop_set[x];
			prop_set[2 * x + 1] = prop_set[x];
			prop_add[2 * x] = 0; prop_add[2 * x + 1] = 0;
		}
		prop_set[x] = -1;
	}
	if(prop_add[x]) {
		if(prop_add[x] >= K)
			T_msk[x].reset();
		else
			T_msk[x] <<= prop_add[x];
		T_sum[x] += (ll)len * prop_add[x];
		if(x < OFF) {
			prop_add[2 * x] += prop_add[x];
			prop_add[2 * x + 1] += prop_add[x];
		}
		prop_add[x] = 0;
	}
}

void update_set(int i, int a, int b, int lo, int hi, int val) {
	if(lo <= a && b <= hi) {
		prop_add[i] = 0; prop_set[i] = val;
		refresh(i, b - a + 1); return;
	}
	refresh(i, b - a + 1);
	if(a > hi || b < lo) return;
	update_set(2 * i, a, (a + b) / 2, lo, hi, val);
	update_set(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, val);
	T_sum[i] = T_sum[2 * i] + T_sum[2 * i + 1];
	T_msk[i] = T_msk[2 * i] | T_msk[2 * i + 1];
}

void update_add(int i, int a, int b, int lo, int hi, int val) {
	if(lo <= a && b <= hi) {
		prop_add[i] += val;
		refresh(i, b - a + 1); return;
	}
	refresh(i, b - a + 1);
	if(a > hi || b < lo) return;
	update_add(2 * i, a, (a + b) / 2, lo, hi, val);
	update_add(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, val);
	T_sum[i] = T_sum[2 * i] + T_sum[2 * i + 1];
	T_msk[i] = T_msk[2 * i] | T_msk[2 * i + 1];
}

ll query_sum(int i, int a, int b, int lo, int hi) {
	refresh(i, b - a + 1);
	if(lo <= a && b <= hi) return T_sum[i];
	if(a > hi || b < lo) return 0;
	return query_sum(2 * i, a, (a + b) / 2, lo, hi) + query_sum(2 * i + 1, (a + b) / 2 + 1, b, lo, hi);
}

bitset < K > ans;
int bio[N], cookie;

void query_msk(int i, int a, int b, int lo, int hi) {
	refresh(i, b - a + 1);
	if(lo <= a && b <= hi) {
		ans |= T_msk[i];
		return;
	}
	if(a > hi || b < lo) return;
	query_msk(2 * i, a, (a + b) / 2, lo, hi);
	query_msk(2 * i + 1, (a + b) / 2 + 1, b, lo, hi);
}

void refresh_interval(int i, int a, int b, int lo, int hi) {
	refresh(i, b - a + 1);
	if(a > hi || b < lo || a == b) return;
	refresh_interval(2 * i, a, (a + b) / 2, lo, hi);
	refresh_interval(2 * i + 1, (a + b) / 2 + 1, b, lo, hi);
}

int get_mex(int l, int r) {
	ans.reset();
	query_msk(1, 0, OFF - 1, l, r);
	int ret = (~ans)._Find_first();
	if(ret == K) {
		cookie++;
		refresh_interval(1, 0, OFF - 1, l, r);
		for(int i = l;i <= r;i++) {
			if(T_sum[OFF + i] < N)
				bio[T_sum[OFF + i]] = cookie;
		}
		ret = 0;
		while(bio[ret] == cookie) ret++;
	}
	return ret;
}

int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0); 
	memset(prop_set, -1, sizeof(prop_set));
	int n, q; scanf("%d%d", &n, &q);
	for(int i = 0;i < n;i++) {
		int x; scanf("%d", &x);
		T_sum[OFF + i] = x;
		if(x < K) T_msk[OFF + i][x] = 1;
	}
	for(int i = OFF - 1; i ;i--) {
		T_sum[i] = T_sum[2 * i] + T_sum[2 * i + 1];
		T_msk[i] = T_msk[2 * i] | T_msk[2 * i + 1];
	}
	for(;q--;) {
		int ty, l, r; scanf("%d%d%d", &ty, &l, &r); l--, r--;
		if(ty == 3) {
			printf("%lld\n", query_sum(1, 0, OFF - 1, l, r));
		} else if(ty == 1) {
			int val; scanf("%d", &val);
			update_set(1, 0, OFF - 1, l, r, val);
		} else {
			int mex = get_mex(l, r);
			update_add(1, 0, OFF - 1, l, r, mex);
		}
	}
	return 0;
}