#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 7;
const int S = sqrt(N) + 7;
int n, m;
int a[N], sum[S], block_len, loc[N], bg[S], ed[S], s, maxn[S];
void modify_change(int k, int x) {
	sum[loc[k]] += x - a[k];
	a[k] = x;
//	maxn[loc[k]] = max(maxn[loc[k]], x);
	maxn[loc[k]] = 0;
	for (int i = bg[loc[k]]; i <= ed[loc[k]]; i++) maxn[loc[k]] = max(maxn[loc[k]], a[i]);
	return;
}
void modify_mod(int l, int r, int x) {
	if (loc[l] == loc[r]) {
		sum[loc[l]] = 0;
		for (int i = l; i <= r; i++) {
			a[i] %= x;
		}
		for (int i = bg[loc[l]]; i <= ed[loc[l]]; i++) {
			sum[loc[l]] += a[i];
			maxn[loc[l]] = max(maxn[loc[l]], a[i]);
		}
	} else {
		for (int i = l; i <= ed[loc[l]]; i++) {
			a[i] %= x;
		}
		sum[loc[l]] = 0;
		maxn[loc[l]] = 0;
		for (int i = bg[loc[l]]; i <= ed[loc[l]]; i++) {
			maxn[loc[l]] = max(maxn[loc[l]], a[i]);
			sum[loc[l]] += a[i];
		}
		for (int i = bg[loc[r]]; i <= r; i++) {
			a[i] %= x;
		}
		sum[loc[r]] = 0;
		maxn[loc[r]] = 0;
		for (int i = bg[loc[r]]; i <= ed[loc[r]]; i++) {
			maxn[loc[r]] = max(maxn[loc[r]], a[i]);
			sum[loc[r]] += a[i];
		}
		for (int i = loc[l] + 1; i <= loc[r] - 1; i++) {
			if (x >= maxn[i]) {
				maxn[i] = 0;
				sum[i] = 0;
				for (int j = bg[i]; j <= ed[i]; j++) {
					a[j] %= x;
				}
				for (int j = bg[i]; j <= ed[i]; j++) {
					sum[i] += a[j];
					maxn[i] = max(maxn[i], a[j]);
				}
			}
		}
	}
}
long long query(int l, int r) {
	long long  ans = 0;
	if (loc[l] == loc[r]) {
		for (int i = l; i <= r; i++)
			ans += a[i];
	} else {
		for (int i = l; i <= ed[loc[l]]; i++)
			ans += a[i];
		for (int i = bg[loc[r]]; i <= r; i++)
			ans += a[i];
		for (int i = loc[l] + 1; i <= loc[r] - 1; i++) {
			ans += sum[i];
		}
	}
	return ans;
}
signed main() {
	cin >> n >> m;
	block_len = sqrt(n);
	s = ceil(1.000 * n / block_len);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		loc[i] = ceil(1.000 * i / block_len);
	}
	for (int i = 1; i <= s; i++) {
		bg[i] = (i - 1) * block_len + 1;
		ed[i] = i * block_len;
	}
	ed[s] = n;
	memset(maxn, 0, sizeof(maxn));
	memset(sum, 0, sizeof(sum));
	for (int i = 1; i <= s; i++) {
		for (int j = bg[i]; j <= ed[i]; j++) {
			sum[i] += a[j];
			maxn[i] = max(maxn[i], a[j]);
		}
	}
	int opt, l, r, x;
	while (m--) {
		cin >> opt;
		if (opt == 1) {
			cin >> l >> r;
			cout << query(l, r) << '\n';
		} else if (opt == 2){
			cin >> l >> r >> x;
			modify_mod(l, r, x);
		} else if (opt == 3) {
			cin >> l >> x;
			modify_change(l, x);
		}
	}
	return 0;
}

瞪了 2 周半了，实在看不出拿错了。