#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define ull unsigned long long

#define rep(k,i,j) for(int k = i;k <= j; ++k)

#define FOR(k,i,j) for(int k = i;k >= j; --k)

inline int read(){

    int x=,f=;   char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}

    while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-''; ch=getchar();}

    return x*f;

}

#define ls rt<<1

#define rs rt<<1|1

const int mxn = 1e5+;

struct T {ll s;int mx;} tr[mxn<<];

int a[mxn],n,q;

inline void build(int rt,int l,int r){

    if(l==r){

        tr[rt].s = tr[rt].mx = a[l];

        return;

    }

    int m = l+r >>;

    build(ls,l,m),build(rs,m+,r);

    tr[rt].s = tr[ls].s + tr[rs].s;

    tr[rt].mx = max(tr[ls].mx,tr[rs].mx);

}

inline void update(int rt,int l,int r,int lp,int rp,int x){

    if(tr[rt].mx < x) return;

    if(lp==rp){

        tr[rt].s = tr[rt].mx %= x;

        return;

    }

    int m = lp+rp >>;

    if(l<=m) update(ls,l,r,lp,m,x);

    if(r>m) update(rs,l,r,m+,rp,x);

    tr[rt].s = tr[ls].s + tr[rs].s;

    tr[rt].mx = max(tr[ls].mx,tr[rs].mx);

}

inline void update1(int rt,int lp,int rp,int k,int y){

    if(lp==rp){

        tr[rt].s = tr[rt].mx = y;

        return;

    }

    int m = lp+rp >>;

    if(k<=m) update1(ls,lp,m,k,y);

    else update1(rs,m+,rp,k,y);

    tr[rt].s = tr[ls].s + tr[rs].s;

    tr[rt].mx = max(tr[ls].mx,tr[rs].mx);

}

inline ll query(int rt,int lp,int rp,int l,int r){

    if(l<=lp&&rp<=r) {return tr[rt].s;}

    int m = lp+rp >>;

    ll ans = ;

    if(l<=m) ans += query(ls,lp,m,l,r);

    if(r>m) ans += query(rs,m+,rp,l,r);

    return ans;

}

int main(){

    n = read(),q = read();

    rep(i,,n) a[i] = read();

    build(,,n);

    while(q--){

        int opt = read();

        if(opt==){

            int l = read(),r = read();

            printf("%lld\n",query(,,n,l,r));

        }

        if(opt==){

            int l = read(),r = read(),x = read();

            update(,l,r,,n,x);

        }

        if(opt==){

            int k = read(),y = read();

            update1(,,n,k,y);

        }

    }

    return ;

}