rt,WA 30pts

#include <bits/stdc++.h>
using namespace std;
int n,m,p,opt,l,r,x,a[114514],bl[114514],sum[114514],block,tag1[114514],tag2[114514];
inline void psd(int x){
	for(int i=(x-1)*block+1;i<=min(n,x*block);i++)
		a[i]=1ll*a[i]*tag1[x]%p,a[i]=(a[i]+tag2[x])%p;
	tag1[x]=1,tag2[x]=0;
}
signed main(){ 
//	freopen("P3373_2.in","r",stdin);
//	freopen("P3373.txt","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>p,block=pow(n,0.46);
    for(int i=1;i<=n;i++) cin>>a[i],bl[i]=(i-1)/block+1,sum[bl[i]]=(sum[bl[i]]+a[i])%p;
	for(int i=1;i<=bl[n];i++) tag1[i]=1;
    while(m--){
    	cin>>opt>>l>>r;
    	if(opt==1){
    		cin>>x;
    		if(tag1[bl[l]]>1||tag2[bl[l]]) psd(bl[l]);
    		for(int i=l;i<=min(r,bl[l]*block);i++)
				a[i]=1ll*a[i]*x%p,sum[bl[i]]=1ll*sum[bl[i]]*x%p;
			if(bl[l]^bl[r]){
				if(tag1[bl[r]]>1||tag2[bl[r]])psd(bl[r]);
				for(int i=(bl[r]-1)*block+1;i<=r;i++)
					a[i]=1ll*a[i]*x%p,sum[bl[i]]=1ll*sum[bl[i]]*x%p;
			}	 
			for(int i=bl[l]+1;i<bl[r];i++)
				tag1[i]=1ll*tag1[i]*x%p,tag2[i]=1ll*tag2[i]*x%p,sum[i]=1ll*sum[i]*x%p;
		}
		else if(opt==2){
			cin>>x;
    		if(tag1[bl[l]]>1||tag2[bl[l]]) psd(bl[l]);
    		for(int i=l;i<=min(r,bl[l]*block);i++)
				a[i]=(a[i]+x)%p,sum[bl[i]]=(sum[bl[i]]+x)%p;
			if(bl[l]^bl[r]){
				if(tag1[bl[r]]>1||tag2[bl[r]]) psd(bl[r]);
				for(int i=(bl[r]-1)*block+1;i<=r;i++)
					a[i]=(a[i]+x)%p,sum[bl[i]]=(sum[bl[i]]+x)%p;
			}	 
			for(int i=bl[l]+1;i<bl[r];i++)
				tag2[i]=(tag2[i]+x)%p,sum[i]=(1ll*sum[i]+1ll*x*block)%p;
		}
		else{
			int ans=0;
    		for(int i=l;i<=min(r,bl[l]*block);i++)
				ans=(1ll*ans+1ll*a[i]*tag1[bl[i]]%p+tag2[bl[i]])%p;
			if(bl[l]^bl[r])
				for(int i=(bl[r]-1)*block+1;i<=r;i++)
					ans=(1ll*ans+1ll*a[i]*tag1[bl[i]]%p+tag2[bl[i]])%p;
			for(int i=bl[l]+1;i<bl[r];i++)
				(ans+=sum[i])%=p;
			cout<<ans<<'\n';
		}
	}
    return 0;
}