#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=400010,M=571373;
int n,m,o,x,y,z,a[N],s[N],lt[N],lg[N],fvv;
void pu(int t){s[t]=(s[t<<1]+s[t<<1|1])%M;}
void pd(int t,int l,int r,int k){
	if(lt[t]||lg[t]!=1){
        lg[t<<1]=lg[t<<1]*lg[t]%M;
        lg[t<<1|1]=lg[t<<1|1]*lg[t]%M;
        lt[t<<1]=(lt[t<<1]*lg[t]%M+lt[t])%M;
        lt[t<<1|1]=(lt[t<<1|1]*lg[t]%M+lt[t])%M;
        s[t<<1]=(s[t<<1]*lg[t]%M+(k-l+1)*lt[t])%M;
        s[t<<1|1]=(s[t<<1|1]*lg[t]%M+(r-k)*lt[t])%M;
        lt[t]=0;lg[t]=1;
	}
}
void b(int t,int l,int r){
	if(l==r){
		s[t]=a[r]%M;
		return ;
	}
	int k=l+r>>1;
	b(t<<1|1,k+1,r);
	b(t<<1,l,k);pu(t);
}
void h1(int t,int l,int r,int x,int y,int z){
	if(l>y||r<x)return ;
	if(l>=x&&r<=y){
		lt[t]=(lt[t]+z)%M;
		s[t]=(s[t]+z*(r-l+1))%M;
		return ;
	}
	int k=l+r>>1;pd(t,l,r,k);
	h1(t<<1,l,k,x,y,z);
	h1(t<<1|1,k+1,r,x,y,z);
	pu(t);
}
void h2(int t,int l,int r,int x,int y,int z){
	if(l>y||r<x)return ;
	if(l>=x&&r<=y){
		lg[t]=lg[t]*z%M;
		lt[t]=lt[t]*z%M;
		s[t]=s[t]*z%M;
		return ;
	}
	int k=l+r>>1;pd(t,l,r,k);
	h2(t<<1,l,k,x,y,z);
	h2(t<<1|1,k+1,r,x,y,z);
	pu(t);
}
int q(int t,int l,int r,int x,int y){
	if(l>y||r<x)return 0;
	if(l>=x&&r<=y)return s[t]%M;
	int k=l+r>>1;pd(t,l,r,k);
	return (q(t<<1,l,k,x,y)+q(t<<1|1,k+1,r,x,y))%M;
}
signed main(){
	scanf("%lld%lld%lld", &n, &m, &fvv);
	for(int i=1; i<=n; i++)scanf("%lld", &a[i]),lg[i]=1;
	b(1,1,n);
	while(m--){
		scanf("%lld%lld%lld", &o, &x, &y);
		if(o==1){
			scanf("%lld", &z);
			h2(1,1,n,x,y,z);
		}else if(o==2){
			scanf("%lld", &z);
			h1(1,1,n,x,y,z);
		}
		else printf("%lld\n", q(1,1,n,x,y));
	}
	return 0;
}