#include<iostream>
using namespace std;
#define ll long long
struct node{ll l,r,n,maxn;
};
ll max(ll a,ll b){
	if (a>b) return a;
	else return b;
}
node tree[500010];
ll a[100010];
void build(ll p,ll l,ll r){
	tree[p].l=l;
	tree[p].r=r;
	if (l==r) {
		tree[p].n=tree[p].maxn=a[l];
		return;
	}
	ll mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tree[p].n=tree[p*2].n+tree[p*2+1].n;
	tree[p].maxn=max(tree[p*2].maxn,tree[p*2+1].maxn);
	return;
}
void update(ll p,ll s){
	int mid=(tree[s].l+tree[s].r)/2;
	if (p==s) return;
	else if (tree[p].l<=mid) update(p,s*2);
	else update(p,s*2+1);
	tree[s].n=tree[s*2+1].n+tree[s*2].n;
	tree[s].maxn=max(tree[s*2].maxn,tree[s*2+1].maxn);
	return;
}
void search(ll l,ll r,ll k,ll s){
	if (tree[s].maxn<k) return;
	if (tree[s].l==tree[s].r){
		tree[s].n=tree[s].n%k;
		tree[s].maxn=tree[s].n;
		update(s,1);
		return;
	}
	ll mid=(tree[s].l+tree[s].r)/2;
	if (l<=mid) search(l,min(mid,r),k,2*s);
	if (r>mid) search(max(mid+1,l),r,k,2*s+1);
	return;
}

ll find(ll l,ll r,ll s){
	if (tree[s].l==l&&r==tree[s].r){
		return tree[s].n;
	}
	ll ans=0;
	ll mid=(tree[s].l+tree[s].r)/2;
	if (l<=mid) ans+=find(l,min(mid,r),2*s);
	if (r>mid) ans+=find(max(mid+1,l),r,2*s+1);
	return ans;
}
void change(ll x,ll y,ll s){
	if (tree[s].l==x&&tree[s].r==x){
		tree[s].n=y;
		tree[s].maxn=y;
		update(s,1);
		return;
	}
	ll mid=(tree[s].l+tree[s].r)/2;
	if (x<=mid) change(x,y,2*s);
	if (x>mid) change(x,y,2*s+1);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); 
	cout.tie(NULL);
	ll n,m;
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	while (m--)
	{
		ll a,l,r;
		cin>>a>>l>>r;
		if (l>r) swap(l,r);
		if (a==1) cout<<find(l,r,1)<<'\n';
		else if (a==2){
			ll k;
			cin>>k;
			search(l,r,k,1);
		}
		else change(l,r,1);
	}
	return 0; 
}

right 14781426619 wrong 14781333060