三十分且ac on #1 #3 #4，玄关求调

#include<bits/stdc++.h>
using namespace std;
using itn = int;
const int N=1e5;
long long MOD=571373;
long long tree[N*4],add[N*4],mul[N*4],a[N*4];
int n,q,m;
void push_up(int p){tree[p]=(tree[p*2]+tree[p*2+1])%MOD;}
void push_down(int s,int t,int p){
//	if(!add[p]&&mul[p]==1) return ;
	int m=s+t>>1;
	tree[p*2]=(tree[p*2]*mul[p])%MOD;
	tree[p*2]=(tree[p*2]+add[p]*(m-s+1))%MOD;
	tree[p*2+1]=(tree[p*2+1]*mul[p])%MOD;
	tree[p*2+1]=(tree[p*2+1]+add[p]*(t-m))%MOD;
	
	add[p*2]*=mul[p];add[p*2+1]*=mul[p];
	add[p*2]+=add[p];add[p*2+1]+=add[p];
	mul[p*2]*=mul[p];mul[p*2+1]*=mul[p];
	
	add[p]=0;mul[p]=1;	

}
void build(int s,int t,int p){
	mul[p]=1;
	if(s==t){
		tree[p]=a[s];
		return ;
	}
	int m=s+t>>1;
	build(s,m,p*2);build(m+1,t,p*2+1);
	push_up(p);
}
void modify_add(int l,int r,int c,int s,int t,int p){
	if(t<l||r<s)	return ;
	if(l<=s&&t<=r){
		tree[p]=(tree[p]+c*(t-s+1))%MOD;
		add[p]+=c;
		return ;
	}
	push_down(s,t,p);
	int m=s+t>>1;
	modify_add(l,r,c,s,m,p*2);
	modify_add(l,r,c,m+1,t,p*2+1);
	push_up(p);
}
void modify_mul(int l,int r,int c,int s,int t,int p){
	if(t<l||r<s)	return ;
	if(l<=s&&t<=r){
		tree[p]=(tree[p]*c)%MOD;
		mul[p]*=c;
		add[p]*=c;
		return ;
	}
	push_down(s,t,p);
	int m=s+t>>1;
	modify_mul(l,r,c,s,m,p*2);
	modify_mul(l,r,c,m+1,t,p*2+1);
	push_up(p);
}
long long query(int l,int r,int s,int t,int p){
	if(t<l||r<s)	return 0;
	if(l<=s&&t<=r)	return tree[p];
	int m=s+t>>1;
	push_down(s,t,p);
	return query(l,r,s,m,p*2)+query(l,r,m+1,t,p*2+1);
}
void print(int s,int t,int p){
	int m=s+t>>1;
	printf("(%d,%d)%d t:%lld a:%lld m:%lld\n",s,t,p,tree[p],add[p],mul[p]);
	if(s==t) return ;
	print(s,m,p*2);print(m+1,t,p*2+1);
}
int main(){
	cin>>n>>q>>MOD;
	for(int i=1;i<=n;i++)	scanf("%lld",&a[i]);
	build(1,n,1);
	int op,x,y,k;
	for(itn i=1;i<=q;i++){
		scanf("%d",&op);
		if(op==1){
			scanf("%d%d%d",&x,&y,&k);
			modify_mul(x,y,k,1,n,1);	
		}
		if(op==2){
			scanf("%d%d%d",&x,&y,&k);
			modify_add(x,y,k,1,n,1);
		}
		if(op==3){
			scanf("%d%d",&x,&y);
			printf("%lld\n",query(x,y,1,n,1)%MOD);
		}
//		print(1,n,1);
//		cout<<endl;
	}
	return 0;
}