#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct Node{long long sum=0,mx=0;};
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,q;cin>>n>>q;vector<long long>a(n);for(auto&x:a)cin>>x;vector<Node>tr(4*n);auto pull=[&](int u){tr[u]={tr[u*2].sum+tr[u*2+1].sum,max(tr[u*2].mx,tr[u*2+1].mx)};};auto build=[&](auto&&self,int u,int l,int r)->void{if(l==r){tr[u]={a[l],a[l]};return;}int m=(l+r)/2;self(self,u*2,l,m);self(self,u*2+1,m+1,r);pull(u);};auto mod=[&](auto&&self,int u,int l,int r,int ql,int qr,long long x)->void{if(qr<l||r<ql||tr[u].mx<x)return;if(l==r){tr[u].sum%=x;tr[u].mx=tr[u].sum;return;}int m=(l+r)/2;self(self,u*2,l,m,ql,qr,x);self(self,u*2+1,m+1,r,ql,qr,x);pull(u);};auto setv=[&](auto&&self,int u,int l,int r,int p,long long x)->void{if(l==r){tr[u]={x,x};return;}int m=(l+r)/2;if(p<=m)self(self,u*2,l,m,p,x);else self(self,u*2+1,m+1,r,p,x);pull(u);};auto sum=[&](auto&&self,int u,int l,int r,int ql,int qr)->long long{if(ql<=l&&r<=qr)return tr[u].sum;int m=(l+r)/2;long long s=0;if(ql<=m)s+=self(self,u*2,l,m,ql,qr);if(qr>m)s+=self(self,u*2+1,m+1,r,ql,qr);return s;};build(build,1,0,n-1);while(q--){int op;cin>>op;if(op==1){int l,r;cin>>l>>r;cout<<sum(sum,1,0,n-1,l-1,r-1)<<'\n';}else if(op==2){int l,r;long long x;cin>>l>>r>>x;mod(mod,1,0,n-1,l-1,r-1,x);}else{int p;long long x;cin>>p>>x;setv(setv,1,0,n-1,p-1,x);}}}