#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+5,M=571373;
int n,q,m;
int a[N],ans[N<<2],tag[N<<2],mutag[N<<2];
int ls(int p)
{
	return p<<1;
}
int rs(int p)
{
	return p<<1|1;
}
void push_up(int p)
{
	ans[p]=ans[ls(p)]+ans[rs(p)];
	ans[p]%=M;
}
void build(int l,int r,int p)
{
	tag[p]=0;
	mutag[p]=1;
	if(l==r)
	{
		ans[p]=l;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,ls(p));
	build(mid+1,r,rs(p));
	push_up(p);
}
void f(int l,int r,int p,int k)
{
	ans[p]=ans[p]+(k*(r-l+1));
	ans[p]%=M; 
	tag[p]=tag[p]+k;
	tag[p]%=M;
}
void muf(int l,int r,int p,int k)
{
	tag[p]*=k;
	tag[p]%=M;
	mutag[p]*=k%M;
	mutag[p]%=M;
	ans[p]*=k;
	ans[p]%=M; 	
}
void push_down(int l,int r,int p)
{
	if(tag[p])
	{
		int mid=(l+r)>>1;
		f(l,mid,ls(p),tag[p]);
		f(mid+1,r,rs(p),tag[p]);
		tag[p]=0;	
	} 
}
void push_mudown(int l,int r,int p)
{
	if(mutag[p]!=1)
	{
		int mid=(l+r)>>1;
		muf(l,mid,ls(p),mutag[p]);
		muf(mid+1,r,rs(p),mutag[p]);
		mutag[p]=1;
	}
}
void update(int n_l,int n_r,int l,int r,int p,int k)
{
	if(n_l<=l&&r<=n_r)
	{
		f(l,r,p,k);
		return;
	}
	push_mudown(l,r,p);
	push_down(l,r,p);
	int mid=(l+r)>>1;
	if(n_l<=mid) update(n_l,n_r,l,mid,ls(p),k);
	if(n_r>mid) update(n_l,n_r,mid+1,r,rs(p),k); 
	push_up(p);
}
void muupdate(int n_l,int n_r,int l,int r,int p,int k)
{
	if(n_l<=l&&r<=n_r)
	{
		muf(l,r,p,k);
		return;
	}
	push_mudown(l,r,p);
	push_down(l,r,p);
	int mid=(l+r)>>1;
	if(n_l<=mid) update(n_l,n_r,l,mid,ls(p),k);
	if(n_r>mid) update(n_l,n_r,mid+1,r,rs(p),k); 
	push_up(p);
}
int chaxun(int n_l,int n_r,int l,int r,int p)
{
	int res=0;
	if(n_l<=l&&r<=n_r) return ans[p];
	push_mudown(l,r,p);
	push_down(l,r,p);
	int mid=(l+r)>>1;
	if(n_l<=mid) res+=chaxun(n_l,n_r,l,mid,ls(p));
	res%=M;
	if(n_r>mid) res+=chaxun(n_l,n_r,mid+1,r,rs(p)); 
	res%=M;
	push_up(p);
	res%=M;
	return res;
}
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>q>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,n,1);
	while(q--)
	{
		int opt;
		cin>>opt;
		if(opt==1)
		{
			int x,y,k;
			cin>>x>>y>>k;
			muupdate(x,y,1,n,1,k);
		}
		else if(opt==2)
		{
			int x,y,k;
			cin>>x>>y>>k;
			update(x,y,1,n,1,k);
		}
		else
		{
			int x,y;
			cin>>x>>y;
			cout<<chaxun(x,y,1,n,1)%M<<endl;
		}
	}
	return 0;
}