分块0pts求调

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int maxn=1e6+5,inf=1e18;
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}
int fpow(int a,int b,int p){if(b==0){return 1;}int res=fpow(a,b/2,p)%p;if(b%2==1){return((res*res)%p*a)%p;}else{return(res*res)%p;}}
int n,a[maxn],L[maxn],R[maxn],val[maxn],pos[maxn],add[maxn],mod,mul[maxn];
void init(){
	int len=sqrt(n);
	int num=n/len;
	if(n%len!=0){
		num++;
	}
	for(int i=1;i<=num;i++){
		L[i]=(i-1)*len+1;
		R[i]=i*len;
	}
	R[num]=n;
	for(int i=1;i<=num;i++){
		for(int j=L[i];j<=R[i];j++){
			pos[j]=i;
			val[i]+=a[j];
		}
		mul[i]=1;
	}
}
void update(int x,int y,int d,int m){
	int b1=pos[x],b2=pos[y];
	if(b1==b2){
		for(int i=x;i<=y;i++){
			a[i]*=m;
			a[i]%=mod;
			val[b1]*=m;
			val[b1]%=mod;
			a[i]+=d;
			a[i]%=mod;
			val[b1]+=d;
			val[b1]%=mod;
		}
	}
	else{
		for(int i=b1+1;i<b2;i++){
			add[i]+=d;
			mul[i]*=m;
			val[i]*=m;
			val[i]%=mod;
			val[i]+=(R[i]-L[i]+1)*d;
			val[i]%=mod;
		}
		for(int i=x;i<=R[b1];i++){
			a[i]*=m;
			a[i]%=mod;
			val[b1]*=m;
			val[b1]%=mod;
			a[i]+=d;
			a[i]%=mod;
			val[b1]+=d;
			val[b1]%=mod;
		}
		for(int i=L[b2];i<=y;i++){
			a[i]*=m;
			a[i]%=mod;
			val[b2]*=m;
			val[b2]%=mod;
			a[i]+=d;
			a[i]%=mod;
			val[b2]+=d;
			val[b2]%=mod;
		}
	}
}
int query(int x,int y){
	int b1=pos[x],b2=pos[y],ans=0;
	if(b1==b2){
		for(int i=x;i<=y;i++){
			ans+=a[i]*mul[b1]+add[b1];
			ans%=mod;
		}
	}
	else{
		for(int i=b1+1;i<b2;i++){
			ans+=val[i];
			ans%=mod;
		}
		for(int i=x;i<=R[b1];i++){
			ans+=a[i]*mul[b1]+add[b1];
			ans%=mod;
		}
		for(int i=L[b2];i<=y;i++){
			ans+=a[i]*mul[b2]+add[b2];
			ans%=mod;
		}
	}
	return ans;
}
signed main(){
	int m;
	cin>>n>>m>>mod;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	init();
	for(int i=1;i<=m;i++){
		int opt,x,y,k;
		cin>>opt>>x>>y;
		if(opt==1){
			cin>>k;
			update(x,y,0,k);
		}
		else if(opt==3){
			cout<<query(x,y)<<endl;
		}
		else{
			cin>>k;
			update(x,y,k,1);
		}
	}
	return 0;
}