#include<bits/stdc++.h>
using namespace std;
#define ls (p<<1)
#define rs (p<<1|1)
#define inf 100005
#define ll long long

int n,m,nl,nr,mod,pos,val;
ll a[inf],tree[inf<<2],t[inf<<2];//t存最大值

void build(int p,int l,int r)
{
	if(l==r){tree[p]=t[p]=a[l];return;}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	tree[p]=tree[ls]+tree[rs];
	t[p]=max(t[ls],t[rs]);
}

ll ans(int p,int l,int r)
{
	if(l>=nl && r<=nr)return tree[p];
	ll sum=0;
	int mid=(l+r)>>1;
	if(nl<=mid)sum+=ans(ls,l,mid);
	if(nr>mid) sum+=ans(rs,mid+1,r) ;
	return sum;
}

void change2(int p,int l,int r)
{
	if(t[p]<mod)return;
	if(l==r){tree[p]%=mod;t[p]=tree[p];return;}
	int mid=(l+r)>>1;
	if(nl<=mid)change2(ls,l,mid);
	if(nr>mid) change2(rs,mid+1,r);
	tree[p]=tree[ls]+tree[rs];
	t[p]=max(t[ls],t[rs]);
}

void change3(int p,int l,int r)
{
	if(l==r){tree[p]=t[p]=val;return;}
	int mid=(l+r)>>1;
	if(pos<=mid)change3(ls,l,mid);
	else change3(rs,mid+1,r);
	tree[p]=tree[ls]+tree[rs];
	t[p]=max(t[ls],t[rs]);
}

int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
	build(1,1,n);
	int rqyy;
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&rqyy);
		if(rqyy==1)
		{
			scanf("%d%d",&nl,&nr);
			printf("%d\n",ans(1,1,n));
		}
		if(rqyy==2)
		{
			scanf("%d%d%d",&nl,&nr,&mod);
			change2(1,1,n);
		}
		if(rqyy==3)
		{
			scanf("%d%d",&pos,&val);
			change3(1,1,n); 
		}
	}
	return 0;
}