代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10, sq = 300;
int n, a[N], L[N], R[N], m, sum[N], pre[N], ba[N], nsq;
multiset<int> st[1000];
inline int que_vio(int l, int r) {
	int now = 0;
	for (int j = l; j <= r; ++j) now += a[j];
	return now;
}
inline void modi_vio(int l, int r, int mod, int num) {
	for (int j = l; j <= r; ++j)
        if (a[j] >= mod) {
            sum[num] -= a[j];
            st[num].erase(a[j]);
            a[j] %= mod;
            st[num].insert(a[j]);
            sum[num] += a[j];
        }
}
inline void modi(int ql, int qr, int mod) {
    int bl = ba[ql], br = ba[qr];
    for (int i = bl + 1; i <= br - 1; ++i) if (*st[i].rbegin() >= mod) modi_vio(L[i], R[i], mod, i);
    if (bl == br) {
        modi_vio(ql, qr, mod, bl);
        return ;
    }
    modi_vio(ql, R[bl], mod, bl);
    modi_vio(L[br], qr, mod, br);
}
inline int que(int ql, int qr) {
    int bl = ba[ql], br = ba[qr], ans = 0;
    if (bl == br) {
        ans += que_vio(ql, qr);
        return ans;
    }
    for (int i = bl + 1; i <= br - 1; ++i) ans += sum[i];
    ans += que_vio(ql, R[bl]);
    ans += que_vio(L[br], qr);
    return ans;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i], pre[i] = pre[i - 1] + a[i];
    for (int i = 1; i <= n; ++i) {
    	++nsq;
        L[i] = R[i - 1] + 1;
        R[i] = i * sq;
		if (R[i] >= n) R[i] = n;
        sum[i] = pre[R[i]] - pre[L[i] - 1];
        for (int j = L[i]; j <= R[i]; ++j) ba[j] = i, st[i].insert(a[j]);
        if (R[i] == n) break;
    }
    while (m--) {
        int op, l, r, k, x, mod;
        cin >> op;
        if (op == 1) {
            cin >> l >> r;
            cout << que(l, r) << '\n';
        }
        if (op == 2) {
            cin >> l >> r >> mod;
            modi(l, r, mod);
        }
        if (op == 3) {
            cin >> k >> x;
            st[ba[k]].erase(a[k]);
            sum[ba[k]] -= a[k];
            a[k] = x;
            st[ba[k]].insert(a[k]);
            sum[ba[k]] += a[k];
        }
    }
    return 0;
}