#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

inline ll read() {
	ll x = 0; bool f = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if(ch == '-') f = 1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return !f ? x : -x;
}

struct Node {
	int ls, rs;
	ll sum, maxn;
};

struct SegmentTree {

	int n, m, opt, l, r, cnt, rt;
	ll v; Node tree[100005 << 4];
	
	void push_up(int p) {
		int ls = tree[p].ls, rs = tree[p].rs;
		tree[p].sum = tree[ls].sum + tree[rs].sum;
		tree[p].maxn = max(tree[ls].maxn, tree[rs].maxn);
	}
	
	void build(int &p, int l, int r) {
		if(!p) p = ++cnt;
		if(l == r) {
			tree[p].sum = tree[p].maxn = read();
			return;
		}
		int mid = (l + r) >> 1;
		build(tree[p].ls, l, mid);
		build(tree[p].rs, mid + 1, r);
		push_up(p);
	}
	
	void update_mod(int p, int nl, int nr, int l, int r, ll P) {
		if(tree[p].maxn < P) return;
		if(nl <= l && r <= nr) {
			tree[p].sum %= P;
			tree[p].maxn %= P;
			return;
		}
		int mid = (l + r) >> 1;
		if(nl <= mid) update_mod(tree[p].ls, nl, nr, l, mid, P);
		if(mid < nr) update_mod(tree[p].rs, nl, nr, mid + 1, r, P);
		push_up(p);
	}
	
	void update(int p, int l, int r, int x, ll v) {
		if(l == r) {
			tree[p].sum = tree[p].maxn = v;
			return;
		}
		int mid = (l + r) >> 1;
		if(x <= mid) update(tree[p].ls, l, mid, x, v);
		else update(tree[p].rs, mid + 1, r, x, v);
		push_up(p);
	}
	
	ll query(int p, int nl, int nr, int l, int r) {
		if(nl <= l && r <= nr) return tree[p].sum;
		int mid = (l + r) >> 1;
		ll ret = 0;
		if(nl <= mid) ret += query(tree[p].ls, nl, nr, l, mid);
		if(mid < nr) ret += query(tree[p].rs, nl, nr, mid + 1, r);
		return ret;
	}
};

SegmentTree T;

int main() {
	T.n = read(); T.m = read();
	T.build(T.rt, 1, T.n);
	while(T.m --) {
		T.opt = read(); T.l = read();
		if(T.opt == 1) {
			T.r = read(); if(T.l > T.r) swap(T.l, T.r);
			printf("%lld\n", T.query(1, T.l, T.r, 1, T.n));
		}
		else if(T.opt == 2) {
			T.r = read(); if(T.l > T.r) swap(T.l, T.r);
			T.v = read();
			T.update_mod(1, T.l, T.r, 1, T.n, T.v);
		}
		else {
			T.v = read();
			T.update(1, 1, T.n, T.l, T.v);
		}
	}
	return 0;
}

部分样例输出是对的，部分是错的，找不到原因，求救