rt

样例过了

// Problem: P3373 【模板】线段树 2
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3373
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define F(i,j,k) for (signed i=signed(j);i<=signed(k);i++)
#define endl '\n'
#define int long long
const int maxn=1e5+5;

int n,block,a[maxn],m,p,x,y,k,op;
int mul[405],add[405],ans[405],id[maxn],fst[maxn];

#define mod(x) ((x)%=p)

void Add(int x,int y,int k){
	if(id[x]==id[y]){
		F(i,x,y) mod(a[i]+=k),mod(ans[id[i]]+=k);
		return;
	}
	for(int i=x;id[i]==id[x];i++) mod(a[i]+=k),mod(ans[id[i]]+=k);
	F(i,id[x]+1,id[y]-1) mod(ans[i]+=k*block),mod(add[i]+=k);
	for(int i=y;id[i]==id[y];i--) mod(a[i]+=k),mod(ans[id[i]]+=k);
}
void push_down(int x){
	for(int i=fst[id[x]];id[i]==id[x];i++) 
		mod(a[i]=a[i]*mul[id[i]]+add[id[i]]);
	mul[id[x]]=1,add[id[x]]=0;
}
void push_up(int x){
	ans[id[x]]=0;
	for(int i=fst[id[x]];id[i]==id[x];i++) mod(ans[id[i]]+=a[i]);
}
void Mul(int x,int y,int k){
	if(id[x]==id[y]){
		push_down(x);
		F(i,x,y) mod(a[i]*=k);
		push_up(x);
		return;
	}
	push_down(x);
	for(int i=x;id[i]==id[x];i++) mod(a[i]*=k);
	push_up(x);
	
	
	F(i,id[x]+1,id[y]-1) mod(ans[i]*=k),mod(add[i]*=k),mod(mul[i]*=k);
	
	push_down(y);
	for(int i=y;id[i]==id[y];i--) mod(a[i]*=k);
	push_up(y);
}
int query(int x,int y){
	int Ans=0;
	if(id[x]==id[y]){
		F(i,x,y) mod(Ans+=a[i]*mul[id[i]]+add[id[i]]);
		return Ans;
	}
	for(int i=x;id[i]==id[x];i++) mod(Ans+=a[i]*mul[id[i]]+add[id[i]]);
	F(i,id[x]+1,id[y]-1) mod(Ans+=ans[i]);
	for(int i=y;id[i]==id[y];i--) mod(Ans+=a[i]*mul[id[i]]+add[id[i]]);
	return Ans;
}

signed main() { 
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>p;
	block=sqrt(n);
	F(i,1,n){
		cin>>a[i];
		id[i]=(i-1)/block+1;
		mul[id[i]]=1;
		ans[id[i]]+=a[i];
		if(!fst[id[i]]) fst[id[i]]=i;
	}
	F(i,1,m){
		cin>>op>>x>>y;
		if(op==1) cin>>k,Mul(x,y,k);
		else if(op==2) cin>>k,Add(x,y,k);
		else cout<<query(x,y)<<endl;
	}
	return 0; 
}