#include<bits/stdc++.h>
#define maxn 1000100
using namespace std;
long long w[maxn],a[maxn],m[maxn],h[maxn];
struct nb{
	long long l,r;
}tree[maxn];
long long p;
long long cnt=0;
long long lazya[maxn],lazym[maxn];
void clazy(long long now,long long len,long long changex,long long changey){
	w[now]=1ll*w[now]*changey%p;
	w[now]=(w[now]+1ll*changex*len)%p;
	lazym[now]=(lazym[now]+changey)%p;
	lazya[now]=1ll*lazya[now]*changey%p;
	lazya[now]=(lazya[now]+changex)%p;
}
void pushup(long long now){//更新
	w[now]=w[now*2]+w[now*2+1];
}
void pushdown(long long now){
	if(lazya[now]==0) return;
	if(lazym[now]==1) return;
	long long mid=(tree[now].l+tree[now].r)/2;
	clazy(now*2,mid-tree[now].l+1,lazya[now],lazym[now]);
	clazy(now*2+1,tree[now].r-mid,lazya[now],lazym[now]);
	lazya[now]=0;
	lazym[now]=1;
}
void build(long long now,long long l,long long r){//建树
	tree[now].l=l,tree[now].r=r;
	if(tree[now].l==tree[now].r){
		w[now]=a[l];
		return;
	}
	long long mid=(l+r)/2;
	build(now*2,l,mid);build(now*2+1,mid+1,r);
	pushup(now);
}
long long findf(long long now,long long target){//单点查询
	if(tree[now].l==tree[now].r)
		return w[now];
	long long mid=(tree[now].l+tree[now].r)/2;
	if(mid>=target)return findf(now*2,target); 
	else return findf(now*2+1,target);		
}
void updatef(long long now,long long target,long long change){//单点修改
	if(tree[now].l==tree[now].r){
		w[now]=change;
		return ;
	}
	long long mid=(tree[now].l+tree[now].r)/2;
	if(mid>=target)updatef(now*2,target,change);
	else updatef(now*2+1,target,change);
	pushup(now);
}
long long findall(long long now,long long left,long long right){//区间查询
	if((tree[now].l>=left)&&(tree[now].r<=right))
		return w[now];
	else if(!(tree[now].l>right||tree[now].r<left)){
		long long mid=(tree[now].l+tree[now].r)/2;
		pushdown(now);
		return findall(now*2,left,right)+findall(now*2+1,left,right); 
	}
	else return 0;
}
void update1(long long now,long long left,long long right,long long change){//区间修改 
	if((tree[now].l>=left)&&(tree[now].r<=right))
		return clazy(now,tree[now].r-tree[now].l+1,0,change);
	else if(!(tree[now].l>right||tree[now].r<left)){
		long long mid=(tree[now].l+tree[now].r)/2;
		pushdown(now);
		update1(now*2,left,right,change);
		update1(now*2+1,left,right,change);
		pushup(now);
	}
}
void update2(long long now,long long left,long long right,long long change){//区间修改 
	if((tree[now].l>=left)&&(tree[now].r<=right))
		return clazy(now,tree[now].r-tree[now].l+1,change,1);
	else if(!(tree[now].l>right||tree[now].r<left)){
		long long mid=(tree[now].l+tree[now].r)/2;
		pushdown(now);
		update2(now*2,left,right,change);
		update2(now*2+1,left,right,change);
		pushup(now);
	}
}
int main(){
	long long n,m;
	cin>>n>>m>>p;
	p=571373;
	for(long long i=1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	for(long long i=1;i<=m;i++){
		long long op,x,y;
		long long k;
		cin>>op;
		if(op==1){
			cin>>x>>y>>k;
			update1(1,x,y,k);
		}
		else if(op==2){
			cin>>x>>y>>k;
			update2(1,x,y,k);
		}
		else{
			cin>>x>>y;
			cout<<findall(1,x,y)<<"\n";
		}
	} 
    return 0;
    
}//不开long long见祖宗