#include<bits/stdc++.h>
using namespace std;
const double pi=3.14;
const int inf=0x3f3f3f3f;
const int NIL=-1;
#define f(i,l,r) for(int i=l;i<=r;i++)
#define MOD 571373
struct Tree{
	int l,r,mid;
	long long value;
	long long lazytag,time_lazytag;
}T[400010];
int n,q;
int a[400010];
int sizex(int x){
	return T[x].r-T[x].l+1;
}
void Pushup(int x){
	T[x].value=T[x*2].value+T[x*2+1].value;
}
void pushdown(int x,bool p){
	if (T[x].l<T[x].r){
		if (p==0){
			T[x*2].value+=sizex(x*2)*T[x].lazytag;
			T[x*2].lazytag+=T[x].lazytag;
			T[x*2+1].value+=sizex(x*2+1)*T[x].lazytag;
			T[x*2+1].lazytag+=T[x].lazytag;
			T[x].lazytag=0;	
		}else{
			T[x*2].value=T[x*2].value*T[x].time_lazytag%MOD;
			T[x*2].time_lazytag=T[x*2].time_lazytag*T[x].time_lazytag%MOD;
			T[x*2].lazytag=T[x*2].lazytag*T[x].lazytag%MOD;
			
			T[x*2+1].value=T[x*2+1].value*T[x].time_lazytag%MOD;
			T[x*2+1].time_lazytag=T[x*2+1].time_lazytag*T[x].time_lazytag%MOD;
			T[x*2+1].lazytag=T[x*2+1].lazytag*T[x].lazytag%MOD;
			
			T[x].time_lazytag=1;
		}
	}
}
void Prepare_Tree(int x,int l,int r){
	T[x].l=l;
	T[x].r=r;
	T[x].mid=(l+r)>>1;
	T[x].time_lazytag=1;
	if (l==r){
		T[x].value=a[l];
	}else{
		Prepare_Tree(x*2,l,T[x].mid);
		Prepare_Tree(x*2+1,T[x].mid+1,r);
		Pushup(x); 
	}
}
void Update(int x,int l,int r,long long add){
	if (T[x].l==l&&T[x].r==r){
		T[x].value+=add*sizex(x);
		T[x].lazytag+=add;
		return;
	}
	pushdown(x,0);
	if (l>T[x].mid) Update(x*2+1,l,r,add);
	else if (r<=T[x].mid) Update(x*2,l,r,add);
	else{
		Update(x*2+1,T[x].mid+1,r,add);
		Update(x*2,l,T[x].mid,add);
	}
	Pushup(x);
}
void Update2(int x,int l,int r,long long num){
	if (T[x].l==l&&T[x].r==r){
		T[x].value*=num%MOD;
		T[x].time_lazytag*=num;
		return;
	}
	pushdown(x,1);
	if (l>T[x].mid) Update2(x*2+1,l,r,num);
	else if (r<=T[x].mid) Update2(x*2,l,r,num);
	else{
		Update2(x*2+1,T[x].mid+1,r,num);
		Update2(x*2,l,T[x].mid,num);
	}
	Pushup(x);
}
long long Getsum(int x,int l,int r){
	if (T[x].l==l&&T[x].r==r){
		return T[x].value;
	}
	pushdown(x,0);
	if (l>T[x].mid) return Getsum(x*2+1,l,r);
	else if (r<=T[x].mid) return Getsum(x*2,l,r);
	else{
		long long res=0;
		res+=Getsum(x*2,l,T[x].mid);
		res+=Getsum(x*2+1,T[x].mid+1,r);
		return res;
	}
}
int read()
{
    int ans=0,flag=1;
    char ch=getchar();
    while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar();
    if(ch=='-') flag=-1,ch=getchar();
    while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
    return ans*flag;
}
int main()
{
	int ljk;
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(),q=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	Prepare_Tree(1,1,n);
	for(int i=1;i<=q;i++){
		int opt=read();
		if(opt==2){
			int f=read(),g=read();
			long long h=read();
			Update(1,f,g,h);
		}else if(opt==3){
			int f=read(),g=read();
			long long res=Getsum(1,f,g);
			cout<<res%MOD<<endl;
		}else if (opt==1){
			int f=read(),g=read();
			long long h=read();
			Update2(1,f,g,h);}
	}
}

目前样例能过，但交上去就是保龄球