RT

#include<iostream>
#define int long long
using namespace std;
const int N=1e5+5,mod=571373; 
int n,m,op;
int a[N],d[N<<2],add[N<<2],mul[N<<2];
int leftson(int x){
	return x<<1;
}
int rightson(int x){
	return x<<1|1; 
}
void pushup(int l,int r,int p,int mid){
	if(mul[p]!=1){
		mul[leftson(p)]=(mul[leftson(p)]*mul[p])%mod;
		mul[rightson(p)]=(mul[rightson(p)]*mul[p])%mod;
		add[leftson(p)]=(add[leftson(p)]*mul[p])%mod;
		add[rightson(p)]=(add[rightson(p)]*mul[p])%mod; 
		d[leftson(p)]=(d[leftson(p)]*mul[p])%mod;
		d[rightson(p)]=(d[rightson(p)]*mul[p])%mod; 
	}
	mul[p]=1;
	if(add[p]){
		d[leftson(p)]=(mid-l+1)*add[p],d[rightson(p)]=(r-mid)*add[p];
		d[leftson(p)]%=mod,d[rightson(p)]%=mod;
		add[leftson(p)]+=add[p],add[rightson(p)]+=add[p];
		add[leftson(p)]%=mod,add[rightson(p)]%=mod;
	}
	add[p]=0;
}
void build(int l,int r,int p){
	mul[p]=1;
	if(l==r){
		d[p]=a[l]%mod;
		return;
	} 
	int mid=(l+r)>>1;
	build(l,mid,leftson(p));
	build(mid+1,r,rightson(p));
	d[p]=(d[leftson(p)]+d[rightson(p)])%mod;
}
void change_add(int L,int R,int l,int r,int p,int k){
	if(L<=l&&r<=R){
		d[p]+=(r-l+1)*k,d[p]%=mod;
		add[p]+=k,add[p]%=mod;
		return;
	}
	int mid=(l+r)>>1;
	pushup(l,r,p,mid);
	if(L<=mid) change_add(L,R,l,mid,leftson(p),k);
	if(R>mid) change_add(L,R,mid+1,r,rightson(p),k);
	d[p]=(d[leftson(p)]+d[rightson(p)])%mod;
}
void change_mul(int L,int R,int l,int r,int p,int k){
	if(L<=l&&r<=R){
		mul[p]*=k,mul[p]%=mod;
		add[p]*=k,add[p]%=mod;
		d[p]*=k,d[p]%=mod; 
		return;
	}
	int mid=(l+r)>>1;
	pushup(l,r,p,mid);
	if(L<=mid) change_mul(L,R,l,mid,leftson(p),k);
	if(R>mid) change_mul(L,R,mid+1,r,rightson(p),k);
	d[p]=(d[leftson(p)]+d[rightson(p)])%mod;
}
int get_sum(int L,int R,int l,int r,int p){
	if(L<=l&&r<=R) return d[p]%mod;
	int mid=(l+r)>>1,sum=0;
	pushup(l,r,p,mid);
	if(L<=mid) sum+=get_sum(L,R,l,mid,leftson(p)),sum%=mod;
	if(R>mid) sum+=get_sum(L,R,mid+1,r,rightson(p)),sum%=mod;
	return sum;
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>m>>op;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,n,1); 
	for(int i=1,l,r,k;i<=m;i++){
		cin>>op>>l>>r;
		if(op==2){
			cin>>k;
			change_add(l,r,1,n,1,k);
		}else if(op==1){
			cin>>k;
			change_mul(l,r,1,n,1,k);
		}else{
			cout<<get_sum(l,r,1,n,1)<<'\n';
		}
	}
}