#include<bits/stdc++.h>

#define int long long
#define mem(x) memset(x,0,sizeof(x))

using namespace std;

int read() {
	int s = 0,w = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if(ch == '-')w = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
	return s * w;
}

struct node {
	int l;
	int r;
	int w;
} e[1000010];

int n,m;
int a[1000010];
int lazy[1000010];
int maxx[1000010];

void merge(int i) {
	e[i].w = e[i * 2].w + e[i * 2 + 1].w;
	maxx[i] = max(maxx[i * 2],maxx[i * 2 + 1]);
}

void build(int i,int l,int r) {
	e[i].l = l;
	e[i].r = r;
	if(l == r) {
		e[i].w = maxx[i] = a[l];
		return ;
	}
	int mid = (l + r) / 2;
	build(i * 2,l,mid);
	build(i * 2 + 1,mid + 1,r);
	merge(i);
}

void update(int i,int x,int y) {
	if(e[i].l == e[i].r) {
		e[i].w = maxx[i] = y;
		return ;
	}
	int mid = (e[i].l + e[i].r) / 2;
	if(x <= mid)update(i * 2,x,y);
	else if(x > mid)update(i * 2 + 1,x,y);
	merge(i);
}

void updatemod(int i,int l,int r,int x) {
	if(maxx[i] < x)return ;
	if(l == r) {
		e[i].w %= x;
		maxx[i] %= x;
		return ;
	}
	int mid = (e[i].l + e[i].r) / 2;
	if(l <= mid)updatemod(i * 2,l,mid,x);
	if(r > mid)updatemod(i * 2 + 1,mid + 1,r,x);
	merge(i);
}

int query(int i,int l,int r) {
	if(e[i].l >= l && e[i].r <= r)return e[i].w;
	int mid = (e[i].l + e[i].r) / 2;
	if(mid >= r)return query(i * 2,l,r);
	else if(mid < l)return query(i * 2 + 1,l,r);
	else return query(i * 2,l,mid) + query(i * 2 + 1,mid + 1,r);
}

signed main() {
	cin>>n>>m;
	for(int i = 1; i <= n; i ++)a[i] = read();
	build(1,1,n);
	for(int i = 1; i <= m; i ++) {
		int op;
		int x,y,w;
		op = read();
		if(op == 1) {
			x = read(),y = read();
			cout<<query(1,x,y)<<endl;
		}
		if(op == 2) {
			x = read(),y = read(),w = read();
			updatemod(1,x,y,w);
		}
		if(op == 3) {
			x = read(),y = read();
			update(1,x,y);
		}
	}
	return 0;
}