#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const ll N=200009/*看这里*/,MOD=571373; 
struct Segment{
	ll l,r,len,toAdd,toMul,sum;
}tr[4*N];
ll n,m,rubbish;
void modi(ll u){
	tr[u].sum%=MOD; tr[u].toAdd%=MOD; tr[u].toMul%=MOD;
}
void pushdown(ll u){
	ll toa=tr[u].toAdd,tom=tr[u].toMul;
	tr[u*2].toMul*=tom; tr[u*2].toAdd*=tom; tr[u*2].sum*=tom;
	tr[u*2].toAdd+=toa; tr[u*2].sum+=(tr[u*2].len*toa);
	modi(u*2);
	
	tr[u*2+1].toMul*=tom; tr[u*2+1].toAdd*=tom; tr[u*2+1].sum*=tom;
	tr[u*2+1].toAdd+=toa; tr[u*2+1].sum+=(tr[u*2+1].len*toa); 
	modi(u*2+1);
	tr[u].toAdd=0; tr[u].toMul=1;
}

void build(ll u,ll l,ll r){//build函数建立线段树，没有他剩下操作都是建立在虚树上，不成立。 
//	cout<<u<<endl; 
	tr[u]=(Segment){l,r,r-l+1,0,1,0};
	if(l==r) return;
	ll mid=(l+r)/2;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
}
void add(ll u,ll l,ll r,ll delta){
	pushdown(u);
	if(tr[u].l>r||tr[u].r<l) return;
	else if(l<=tr[u].l&&tr[u].r<=r){
		tr[u].toAdd+=delta;
		tr[u].sum+=(tr[u].len*delta);
		modi(u);
		return;
	}
	add(u*2,l,r,delta); add(u*2+1,l,r,delta);
	tr[u].sum=tr[u*2].sum+tr[u*2+1].sum;
	modi(u);
}

void mul(ll u,ll l,ll r,ll delta){
	pushdown(u);
	if(tr[u].l>r||tr[u].r<l) return;
	else if(l<=tr[u].l&&tr[u].r<=r){
		tr[u].toAdd*=delta; tr[u].toMul*=delta; tr[u].sum*=delta;
		modi(u);
		return;
	}
	mul(u*2,l,r,delta); mul(u*2+1,l,r,delta);
	tr[u].sum=tr[u*2].sum+tr[u*2+1].sum;
	modi(u);
}

ll query(ll u,ll l,ll r){
	pushdown(u);
	if(tr[u].l>r||tr[u].r<l) return 0;
	else if(l<=tr[u].l&&tr[u].r<=r) return tr[u].sum;
	return (query(u*2,l,r)%MOD+query(u*2+1,l,r)%MOD)%MOD;
}
int main(){
	cin>>n>>m>>rubbish;
	build(1,1,n);
	for(ll i=1,qwq;i<=n;i++){
		cin>>qwq;//创建临时变量以节省空间（0.76MB） 
		add(1,i,i,qwq);
	}
	for(ll i=1;i<=m;i++){
		ll opt,x,y,k;
		cin>>opt>>x>>y;
		if(opt==1){
			cin>>k; mul(1,x,y,k);
		}
		else if(opt==2){
			cin>>k;
			add(1,x,y,k);
		}
		else{
			cout<<query(1,x,y)%MOD<<endl;
		}
	}
    return 0;
}