#include <bits/stdc++.h>
#define fo(x,a,b) for(register int (x)=(a);(x)<=(b);++(x))
#define lc p<<1
#define rc p<<1|1
#define int long long
using namespace std;
const int M=1e5+3,mod=571373;
struct node{
	int l,r,v,add,mult;
}t[4*M];
int a[M],q,x,y,k;
void build(int l,int r,int p){
	t[p]={l,r,a[l]};
	if(l==r) return;
	int m=l+r>>1;
	build(l,m,lc);
	build(m+1,r,rc);
	t[p].v=(t[lc].v+t[rc].v)%mod;
}
void pushdown(int p){
	if(t[p].add){
		t[lc].v+=(t[p].add*(t[lc].r-t[lc].l+1))%mod;
		t[rc].v+=(t[p].add*(t[rc].r-t[rc].l+1))%mod;
		t[lc].add+=t[p].add;
		t[rc].add+=t[p].add;
		t[p].add=0;
	}
	if(t[p].mult){
		t[lc].v=(t[p].mult*t[lc].v)%mod;
		t[rc].v=(t[p].mult*t[rc].v)%mod;
		t[lc].mult+=t[p].mult;
		t[rc].mult+=t[p].mult;
		t[p].mult=0;
	}
}
int query(int l,int r,int p){
	if(t[p].l>=l&&t[p].r<=r)return t[p].v;
	int ans=0;
	pushdown(p);
	int m=t[p].l+t[p].r>>1;
	if(m>=l) ans+=query(l,r,lc);
	if(m<r) ans+=query(l,r,rc);
	return ans%mod;
} 
void update_mult(int l,int r,int p,int k){
	if(t[p].l>=l&&t[p].r<=r){
		t[p].v=(k*t[p].v)%mod;	
		t[p].mult+=k;
		return;
	}
	int m=t[p].l+t[p].r>>1;
	pushdown(p);
	if(m>=l) update_mult(l,r,lc,k);
	if(m<r) update_mult(l,r,rc,k);
	t[p].v=(t[lc].v+t[rc].v)%mod;
}
void update_add(int l,int r,int p,int k){
	if(t[p].l>=l&&t[p].r<=r){
		t[p].v+=(k*(t[p].r-t[p].l+1))%mod;
		t[p].add+=k;
		return;
	}
	int m=t[p].l+t[p].r>>1;
	pushdown(p);
	if(m>=l) update_add(l,r,lc,k);
	if(m<r) update_add(l,r,rc,k);
	t[p].v=(t[lc].v+t[rc].v)%mod;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m,b;
	cin>>n>>m>>b;
	fo(i,1,n)cin>>a[i];
	build(1,n,1);
	fo(i,1,m){
		cin>>q;
		if(q==1){
			cin>>x>>y>>k;
			update_mult(x,y,1,k);
		}else if(q==2){
			cin>>x>>y>>k;
			update_add(x,y,1,k);
		}else{
			cin>>x>>y;
			cout<<query(x,y,1)<<"\n";
		}
	}
	return 0;
}