30pts WA 求条悬一关

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,q,a[N],p,op,x,y,z;
struct node{
	int l,r,sum,add,mul;
}t[N*4];
void pushup(int rt){ 
	t[rt].sum=(t[rt<<1].sum+t[rt<<1|1].sum)%p;
	return;
}
void pushdown(int rt){
	t[rt<<1].sum=(t[rt<<1].sum*t[rt].mul+t[rt].add*(t[rt<<1].r-t[rt<<1].l+1))%p;
	t[rt<<1|1].sum=(t[rt<<1|1].sum*t[rt].mul+t[rt].add*(t[rt<<1|1].r-t[rt<<1|1].l+1))%p;
	t[rt<<1].mul=(t[rt<<1].mul*t[rt].mul)%p;
	t[rt<<1|1].mul=(t[rt<<1|1].mul*t[rt].mul)%p;
	t[rt<<1|1].mul=(t[rt<<1|1].mul*t[rt].mul)%p;
	t[rt<<1].add=(t[rt<<1].add*t[rt].mul+t[rt].add)%p;
	t[rt<<1|1].add=(t[rt<<1|1].add*t[rt].mul+t[rt].add)%p;
	t[rt].add=0,t[rt].mul=1;
	return;
}
void init(int l,int r,int rt=1){
	t[rt].l=l,t[rt].r=r,t[rt].mul=1;
	if(l==r){
		t[rt].sum=a[l]%p;
		return;
	} 
	int mid=(l+r)>>1;
	init(l,mid,rt<<1);
	init(mid+1,r,rt<<1|1);
	pushup(rt);
	return;
}
int query(int l,int r,int rt=1){
	if(t[rt].l>=l&&t[rt].r<=r) return t[rt].sum;
	pushdown(rt);
	int ans=0,mid=(t[rt].l+t[rt].r)>>1;
	if(l<=mid) ans=(ans+query(l,r,rt<<1)%p)%p;
	if(r>mid) ans=(ans+query(l,r,rt<<1|1)%p)%p;
	return ans;
}
void modifyadd(int l,int r,int x,int rt=1){
	if(t[rt].l>=l&&t[rt].r<=r){
		t[rt].add=(t[rt].add+x)%p;
		t[rt].sum=(t[rt].sum+x*(t[rt].r-t[rt].l+1))%p;
		return;
	}
	pushdown(rt);
	int mid=(t[rt].l+t[rt].r)>>1;
	if(l<=mid) modifyadd(l,r,x,rt<<1);
	if(r>mid) modifyadd(l,r,x,rt<<1|1);
	pushup(rt);
}
void modifymul(int l,int r,int x,int rt=1){
	if(t[rt].l>=l&&t[rt].r<=r){
		t[rt].add=(t[rt].add*x)%p;
		t[rt].mul=(t[rt].mul*x)%p;
		t[rt].sum=(t[rt].sum*x)%p;
		return;
	}
	pushdown(rt);
	int mid=(t[rt].l+t[rt].r)>>1;
	if(l<=mid) modifymul(l,r,x,rt<<1);
	if(r>mid) modifymul(l,r,x,rt<<1|1);
	pushup(rt);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q>>p;
	for(int i=1;i<=n;i++) cin>>a[i];
	init(1,n);
	while(q--){
		cin>>op;
		if(op==1){
			cin>>x>>y>>z;
			modifymul(x,y,z,1);
		}else if(op==2){
			cin>>x>>y>>z;
			modifyadd(x,y,z,1);
		}else{
			cin>>x>>y;
			cout<<query(x,y)<<"\n";
		}
	}
	return 0;
}