#include<bits/stdc++.h>
#define int long long
#define lson lc,l,mid
#define rson rc,mid+1,r
using namespace std;

const int MAXN=1e6+100;
const int MOD=571373;
struct node{
	int msg,add,mul;	
}e[MAXN]; 
int n,m,q,a[MAXN];
void build(int k,int l,int r)
{
	e[k].mul=1;
	if(l==r)
	{
		e[k].msg=a[l]%MOD;
		return;
	}
	int mid=(l+r)>>1;
	int lc=k<<1,rc=k<<1|1;
	build(lson);
	build(rson);
	e[k].msg=(e[lc].msg+e[rc].msg)%MOD;
}
void lzplus(int k,int l,int r,int v)
{
	(e[k].msg+=v*(r-l+1))%MOD;
	(e[k].add+=v)%MOD;
}
void lzmul(int k,int l,int r,int v)
{
	(e[k].msg*=v)%MOD;
	if(e[k].add) 
		(e[k].add*=v)%MOD;
	(e[k].mul*=v)%MOD;
}
void push_down(int k,int l,int r)
{                                
	int lc=k<<1,rc=k<<1|1,mid=(l+r)>>1;
	if(e[k].mul!=1)
	{
		lzmul(lson,e[k].mul);
		lzmul(rson,e[k].mul);
		e[k].mul=1; 
	}
	if(e[k].add)
	{
		lzplus(lson,e[k].add);
		lzplus(rson,e[k].add);
		e[k].add=0;
	} 
}
void updata(int tag,int x,int y,int k,int l,int r,int v)
{
	if(x<=l&&r<=y)//in the interval
	{
		if(tag==2)lzplus(k,l,r,v);
		if(tag==1)lzmul(k,l,r,v);
		return ;
	}
	push_down(k,l,r);
	int mid=(l+r)>>1;
	int lc=k<<1,rc=k<<1|1;
	if(x<=mid)updata(tag,x,y,lson,v);
	if(y>mid)updata(tag,x,y,rson,v);
	e[k].msg=(e[lc].msg+e[rc].msg)%MOD;
}
int query(int x,int y,int k,int l,int r)
{
	if(x<=l&&r<=y)
	{
		return e[k].msg%MOD;
	}
	push_down(k,l,r);
	int mid=(l+r)>>1,lc=k<<1,rc=k<<1|1;
	int ret=0;
	if(x<=mid)ret=(ret+query(x,y,lson))%MOD;
	if(y>mid)ret=(ret+query(x,y,rson))%MOD; 
	return ret%MOD;
}
signed main()
{
//	freopen("segment_tree_model2.in","r",stdin);
//	freopen("segment_tree_model2.out","w",stdout);
	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,1,n);
	while(q--)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int x,y,v;cin>>x>>y>>v;
		
			updata(op,x,y,1,1,n,v);
		}else if(op==2)
		{
			int x,y,v;cin>>x>>y>>v;
		
			updata(op,x,y,1,1,n,v);
		}else if(op==3){
			int x,y;cin>>x>>y;
			cout<<query(x,y,1,1,n)<<'\n';
		}
	}
	return 0;
}
/*
5 2 1
571374 571374 571374 571374 571374
1 4 571374
3 1 5

*/