int n,m;ll nnum[100000 + 55];typedef struct Node { int l,r; ll sum; ll maxn;};Node tree[100000 * 4 + 55];void init() { memset(nnum,0,sizeof(nnum));}bool input() { while(cin>>n>>m) { for(int i=1;i<=n;i++)scanf("%Id",&nnum[i]); return false; } return true;}void push_up(int id) { tree[id].sum = tree[id<<1].sum + tree[id<<1|1].sum; tree[id].maxn = max(tree[id<<1].maxn,tree[id<<1|1].maxn);}void build(int l,int r,int id) { tree[id].l = l; tree[id].r = r; tree[id].maxn = 0; tree[id].sum = 0; if(l == r) { tree[id].maxn = nnum[l]; tree[id].sum = nnum[l]; return ; } int mid = (l + r)>>1; build(l,mid,id<<1); build(mid+1,r,id<<1|1); push_up(id);}ll query(int l,int r,int id) { if(tree[id].l == l && tree[id].r == r)return tree[id].sum; int mid = (tree[id].l + tree[id].r)>>1; if(r <= mid) return query(l,r,id<<1); else if(l > mid) return query(l,r,id<<1|1); else return query(l,mid,id<<1) + query(mid + 1,r,id<<1|1);}void update(int l,int r,ll x,int id) { if(tree[id].maxn < x) return ; int mid = (tree[id].l + tree[id].r)>>1; if(tree[id].l == tree[id].r) { tree[id].sum %= x; tree[id].maxn = tree[id].sum; return ; } if(r <= mid)update(l,r,x,id<<1); else if(l > mid)update(l,r,x,id<<1|1); else { update(l,mid,x,id<<1); update(mid + 1,r,x,id<<1|1); } push_up(id);}void update2(int pos,int val,int id) { if(tree[id].l == tree[id].r) { tree[id].sum = tree[id].maxn = val; return ; } int mid = (tree[id].l + tree[id].r)>>1; if(pos <= mid)update2(pos,val,id<<1); else update2(pos,val,id<<1|1); push_up(id);}void cal() { build(1,n,1); int q = m; while(q--) { int type; scanf("%d",&type); if(type == 1) { int l,r; scanf("%d %d",&l,&r); ll ans = query(l,r,1); printf("%Id\n",ans); } else if(type == 2) { int l,r; ll x; scanf("%d %d %Id",&l,&r,&x); update(l,r,x,1); } else { int k,x; scanf("%d %d",&k,&x); update2(k,x,1); } }}void output() {}int main() { while(true) { init(); if(input())return 0; cal(); output(); } return 0;}