#include <bits/stdc++.h>
using namespace std;
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]) {
		for (int i = l; i <= r; i++) {
			sum[loc[l]] = sum[loc[l]] - a[i] + (a[i] % x);
			a[i] %= x;
		}
	} else {
		for (int i = l; i <= ed[loc[l]]; i++) {
			sum[loc[l]] = sum[loc[l]] - a[i] + (a[i] % x);
			a[i] %= x;
		}
		for (int i = bg[loc[r]]; i <= r; i++) {
			sum[loc[r]] = sum[loc[r]] - a[i] + (a[i] % x);
			a[i] %= x;
		}
		for (int i = bg[loc[r]]; i <= r; i++) {
			sum[loc[r]] = sum[loc[r]] - a[i] + (a[i] % x);
			a[i] %= x;
		}
		for (int i = loc[l] + 1; i <= loc[r] - 1; i++) {
			if (x >= maxn[i]) {
				for (int j = bg[loc[i]]; j <= ed[loc[i]]; j++) {
					sum[loc[i]] = sum[loc[i]] - a[j] + (a[j] % x);
					a[j] %= x;
				}
			}
		}
	}
}
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;
}
int 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;
}

RT，改了又改，但一直WA on #3 过不去。