30ptsWA QAQ

#include<bits/stdc++.h> 
#define itn int
#define int long long
#define Max(a,b) (a>b?a:b)
#define Min(a,b) (a<b?a:b)
using namespace std;
const int N=2e5+10;
const int m=571373;
int n,q,sn;
int block[N],sum[N],lazy[N],a[N];
int lazypp[N];
void upp(itn l,int r,int x){
	for(itn i=(block[l]-1)*sn+1;i<=Min(block[l]*sn,n);i++){
		a[i]=a[i]*lazypp[block[i]]%m + lazy[block[i]];
	}
	lazypp[block[l]]=1;
	lazy[block[l]]=0;
	for(int i=l;i<=Min(r,block[l]*sn);i++){
		sum[block[i]]+=(a[i]*(x-1))%m;
		a[i]*=x%m;
	}if(block[l]==block[r]) return;
	for(itn i=(block[r]-1)*sn+1;i<=Min(block[r]*sn,n);i++){
		a[i]=a[i]*lazypp[block[i]]%m + lazy[block[i]];
	}
	lazypp[block[r]]=1;
	lazy[block[r]]=0;
	for(int i= ( (block[r]-1)*sn+1);i<=r;i++){
		sum[block[i]]+=(a[i]*(x-1))%m;
		a[i]*=x%m;
	}
	for(itn i=block[l]+1;i<=block[r]-1;i++){
		lazy[i]*=x%m;
		lazypp[i]*=x%m;
		sum[i]*=x%m;
	}
}
void add(itn l,int r,int x){
	for(itn i=(block[l]-1)*sn+1;i<=Min(block[l]*sn,n);i++){
		a[i]=a[i]*lazypp[block[i]]%m + lazy[block[i]]%m;
	}
	lazypp[block[l]]=1;
	lazy[block[l]]=0;
	for(int i=l;i<=Min(r,block[l]*sn);i++){
		sum[block[i]]+=x%m;
		sum[block[i]]%=m;
		a[i]+=x%m;
	}if(block[l]==block[r])  return ;
	for(itn i=(block[r]-1)*sn+1;i<=Min(block[r]*sn,n);i++){
			a[i]=a[i]*lazypp[block[i]]%m + lazy[block[i]]%m;
		}
	lazypp[block[r]]=1;
	lazy[block[r]]=0;
	for(int i= ( (block[r]-1)*sn+1);i<=r;i++){
		sum[block[i]]+=x;
		sum[block[i]]%=m;
		a[i]+=x%m;
	}
	for(itn i=block[l]+1;i<=block[r]-1;i++){
		lazy[i]+=x%m;
		sum[i]+=sn*x%m;
	}
}
int query(int l,int r){
	int ans=0;
		
	for(int i=l;i<=Min(r,block[l]*sn);i++){
		ans+=a[i]*lazypp[block[i]]%m;
		ans+=lazy[block[i]]%m;
		ans%=m;
	}if(block[l]==block[r])  return ans%m;
	for(int i= ( (block[r]-1)*sn+1);i<=r;i++){
		ans+=a[i]*lazypp[block[i]]%m;
		ans+=lazy[block[i]]%m;
		ans%=m;
	}
	for(itn i=block[l]+1;i<=block[r]-1;i++){
		ans+=sum[i]%m;
		ans%=m;
	}
	return ans%m;
}
signed main(){
	int x;
	cin>>n>>q>>x;
	sn=sqrt(n);
	for(int i=1;i<=n;i++){
		block[i]=(i-1)/sn+1;
	}
	for(itn i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum[block[i]]+=a[i]%m;
		lazypp[block[i]] = 1;
	}
	int op,y,k;
	for(itn i=1;i<=q;i++){
		cin>>op>>x>>y;
		if(op==1){
			cin>>k;
			upp(x,y,k);
		}if(op==2){
			cin>>k;
			add(x,y,k);
		}if(op==3){
			printf("%lld\n",query(x,y));
		}
	}
}