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

const int maxn = 1e5+7;
const int maxx = 0x3f3f3f3f;
int s[maxn];
int blo,pos[maxn];

int n,q;

int Min[maxn];

int tag[maxn];

ll sum[maxn];

void push_downl(int l,int mod){
    Min[pos[l]]=-maxx;
    sum[pos[l]]=0;
    for(int i=l;i<=pos[l]*blo;i++) s[i]=s[i]%mod;
    for(int i=(pos[l]-1)*blo+1;i<=min(n,pos[l]*blo);i++) Min[pos[l]]=max(Min[pos[l]],s[i]),sum[pos[i]]+=s[i];
}
void push_downr(int r,int mod){
    Min[pos[r]]=-maxx;
    sum[pos[r]]=0;
    for(int i=(pos[r]-1)*blo+1;i<=r;i++) s[i]=s[i]%mod;
    for(int i=(pos[r]-1)*blo+1;i<=min(n,pos[r]*blo);i++) Min[pos[r]]=max(Min[pos[r]],s[i]),sum[pos[r]]+=s[i];
}

void push_down(int l,int r,int mod){
    Min[pos[l]]=-maxx;
    sum[pos[l]]=0;
    for(int i=l;i<=r;i++) s[i]=s[i]%mod;
    for(int i=(pos[r]-1)*blo+1;i<=min(n,pos[r]*blo);i++) Min[pos[r]]=max(Min[pos[r]],s[i]),sum[pos[r]]+=s[i];
}

void update(int l,int r,int mod){
    for(int i=pos[l]+1;i<=pos[r]-1;i++){
        if(Min[i]>=mod) {
            Min[i]=-maxx;
            sum[i]=0;
            for(int j=(i-1)*blo+1;j<=min(i*blo,n);j++) s[j]=s[j]%mod,Min[i]=max(s[j],Min[i]),sum[i]+=s[j];
        }
    }
    if(pos[l]!=pos[r]) push_downl(l,mod),push_downr(r,mod);
    else push_down(l,r,mod);
}

void change(int id,int x){
    Min[pos[id]]=-maxx;
    s[id]=x;
    sum[pos[id]]=0;
    for(int i=(pos[id]-1)*blo+1;i<=min(n,pos[id]*blo);i++) Min[pos[id]]=max(Min[pos[id]],s[i]),sum[pos[id]]+=s[i];
}

void query(int l,int r){

    ll ans=0;
    for(int i=pos[l]+1;i<=pos[r]-1;i++) ans+=sum[i];

    if(pos[l]!=pos[r]){
        for(int i=(pos[r]-1)*blo+1;i<=r;i++) ans+=s[i];
        for(int i=l;i<=pos[l]*blo;i++) ans+=s[i];
    }
    else {
        for(int i=l;i<=r;i++) ans+=s[i];
    }

    printf("%lld\n",ans);
}
/**
5 5
1 2 3 4 5
2 3 5 4
3 3 5
*/

int main(){
    scanf("%d %d",&n,&q);blo=(int)sqrt(n*1.0);
    for(int i=1;i<=n;i++) scanf("%d",&s[i]),pos[i]=(i-1)/blo+1;
    for(int i=1;i<=pos[n];i++) Min[i]=-maxx,sum[i]=0;
    for(int i=1;i<=pos[n];i++) {
            for(int j=(i-1)*blo+1;j<=min(i*blo,n);j++) {
                Min[i]=max(Min[i],s[j]),sum[i]+=s[j];
            }

    }

    while(q--){
        int op,l,r,x,id;scanf("%d",&op);
        if(op==1) scanf("%d %d",&l,&r),query(l,r);
        else if(op==2) scanf("%d %d %d",&l,&r,&x),update(l,r,x);
        else if(op==3) scanf("%d %d",&id,&x),change(id,x);
     }
    return 0;
}
