#include <bits/stdc++.h>
using namespace std;
long long inline read(){
	long long x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}
long long n,m,a[2000000];
long long q=571373;
struct tree{
	long long sum;
	long long l,r,mla,pla;
}tr[4000000];
void build(long long num,long long l,long long r){
	tr[num].l=l;
	tr[num].r=r;
	tr[num].mla=1;
	if(l==r){
		tr[num].sum=a[l]%q;
		return;
	}
	long long mid=(l+r)>>1;
	build(num*2,l,mid);
	build(num*2+1,mid+1,r);
	tr[num].sum=(tr[num*2].sum+tr[num*2+1].sum)%q;
}
void spread(long long num){
	long long m=tr[num].mla,p=tr[num].pla;
	tr[num*2].sum=tr[num*2].sum*m%q;
	tr[num*2].sum=tr[num*2].sum+(tr[num*2].r-tr[num*2].l+1)*p%q;
	tr[num*2+1].sum=tr[num*2+1].sum*m%q;
	tr[num*2+1].sum=tr[num*2+1].sum+(tr[num*2+1].r-tr[num*2+1].l+1)*p%q;
	tr[num*2].mla=tr[num*2].mla*m%q;
	tr[num*2].pla=tr[num*2].pla*m+p%q;
	tr[num*2+1].mla=tr[num*2+1].mla*m%q;
	tr[num*2+1].pla=tr[num*2+1].pla*m+p%q;
	tr[num].mla=1;
	tr[num].pla=0;
}
void add1(long long num,long long l,long long r,long long c){
	if(tr[num].l>=l && tr[num].r<=r){
		tr[num].sum=tr[num].sum*c%q;
		tr[num].pla=tr[num].pla*c%q;
		tr[num].mla=tr[num].mla*c%q; 
		return;
	}
	spread(num);
	long long mid=(tr[num].l+tr[num].r)>>1;
	if(mid>=l){
		add1(num*2,l,r,c);
	}
	if(mid<r){
		add1(num*2+1,l,r,c);
	}
	tr[num].sum=(tr[num*2].sum+tr[num*2+1].sum)%q;
} 
void add2(long long num,long long l,long long r,long long j){
	if(tr[num].l>=l && tr[num].r<=r){
		tr[num].sum=(tr[num].sum+(tr[num].r-tr[num].l+1)*j)%q;
		tr[num].pla=(tr[num].pla+j)%q; 
		return;
	}
	spread(num);
	long long mid=(tr[num].l+tr[num].r)>>1;
	if(mid>=l){
		add2(num*2,l,r,j);
	}
	if(mid<r){
		add2(num*2+1,l,r,j);
	}
	tr[num].sum=(tr[num*2].sum+tr[num*2+1].sum)%q;
} 
long long find(long long num,long long x,long long y){
	long long o=0;
	if(tr[num].l>=x && tr[num].r<=y){
		return tr[num].sum%q;
	} 
	spread(num);
	long long mid=(tr[num].l+tr[num].r)>>1;
	if(mid>=x)
		o=(o+find(num*2,x,y))%q;
	if(mid<y)
		o=(o+find(num*2+1,x,y))%q;
	return o%q;
}
int main(){
//	for(int i=1;i<=4000000;i++){
//		tr[i].mla=1;
//	} 
//	freopen("2.in","r",stdin);
//	freopen("2.out","w",stdout);
	n=read();
	m=read();
	q=read();
	for(long long i=1;i<=n;i++){
		a[i]=read();
	}
	build(1,1,n);
	for(long long i=1;i<=m;i++){
		long long k=read();
		if(k==1){
			long long x,y;
			long long c;
			x=read();
			y=read();
			c=read();
			add1(1,x,y,c);
		}
		if(k==2){
			long long x,y,j;
			x=read();
			y=read();
			j=read();
			add2(1,x,y,j);
		}
		if(k==3){
			long long x,y;
			x=read();
			y=read();
			printf("%lld\n",find(1,x,y)%q);
		}
	}
	return 0;
}

rt