#4 TLE求助

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
const int MAXN=1e5+9,MAXT=4e5+9;
typedef long long ll;
struct Tree{
	int ls,rs;
	ll maxn,w;
}tree[MAXT];
int n,m,num_tree=1;
ll a[MAXN];
inline ll read(){
	register ll x=0,f=1;register char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}void push_up(int now){
	tree[now].w=tree[tree[now].ls].w+tree[tree[now].rs].w;
	tree[now].maxn=max(tree[tree[now].ls].maxn,tree[tree[now].rs].maxn);
}void build(int now,int l,int r){
	if(l==r){
		tree[now].w=tree[now].maxn=a[l];
		return;
	}int mid=(l+r)/2;
	tree[now].ls=++num_tree;
	tree[now].rs=++num_tree;
	build(tree[now].ls,l,mid);
	build(tree[now].rs,mid+1,r);
	push_up(now);
}void update(int now,int l,int r,int x,ll k){
	if(l==x&&r==x){
		tree[now].w=tree[now].maxn=k;
		return;
	}int mid=(l+r)/2;
	if(x<=mid)update(tree[now].ls,l,mid,x,k);
	else update(tree[now].rs,mid+1,r,x,k);
	push_up(now);
}void update2(int now,int l,int r,int lx,int rx,ll mods){
	if(lx<=l&&r<=rx&&l==r){
		if(mods<=tree[now].maxn){
			tree[now].maxn%=mods;
			tree[now].w%=mods;
		}return;
	}int mid=(l+r)/2;
	if(lx<=mid)update2(tree[now].ls,l,mid,lx,rx,mods);
	if(rx>mid)update2(tree[now].rs,mid+1,r,lx,rx,mods);
	push_up(now);
}ll query(int now,int l,int r,int lx,int rx){
	ll ans=0;
	if(lx<=l&&r<=rx){
		return tree[now].w;
	}int mid=(l+r)/2;
	if(lx<=mid)ans+=query(tree[now].ls,l,mid,lx,rx);
	if(rx>mid)ans+=query(tree[now].rs,mid+1,r,lx,rx);
	return ans;
}
int main(){
	n=read();
	m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}build(1,1,n);
	for(int i=1;i<=m;i++){
		int opt,l,r,k;
		opt=read();l=read();r=read();
		if(opt==1){
			printf("%lld\n",query(1,1,n,l,r));
		}else if(opt==2){
			k=read();
			update2(1,1,n,l,r,k);
		}else if(opt==3){
			update(1,1,n,l,r);
		}
	}
	return 0;
}