rt，P3373，线段树板子，不需要调qwq
对于 $100\%$ 的数据：$1 \le n \le 10^5$，$1 \le q \le 10^5$。
分块，分析的是$O(q \times \sqrt n)$为啥会T？有的点本地能跑到3s

#include<bits/stdc++.h>
#define int __int128
using namespace std;
const int N=1e5+10,Q=1e5+10;
int n,q,MOD;
int id[N],st[N],ed[N],sum[N],tgp[N],tga[N];
long long a[N];
int sz,cnt=0;
inline 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<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
void write(int x){
	if(x<10){
		putchar(x+'0');
		return;
	}
	write(x/10);
	putchar(x%10+'0');
	return;
}
void reset(int x){
	for(int i=st[x];i<=ed[x];i++){
		a[i]*=tga[x];a[i]%=MOD;
		a[i]+=tgp[x];a[i]%=MOD;
	}
	tga[x]=1,tgp[x]=0;
	return;
}
void And(int l,int r,int k){
	reset(id[l]);
	int lid=id[l],rid=id[r];
	for(int i=l;id[i]==lid;i++){
		sum[id[i]]+=((k-1)*a[i])%MOD;sum[id[i]]%=MOD;
		a[i]*=k;a[i]%=MOD;
	}
	for(int i=lid+1;i<rid;i++){
		tgp[i]*=k;tgp[i]%=MOD;
		tga[i]*=k;tga[i]%=MOD;
		sum[i]*=k;sum[i]%=MOD;
	}
	reset(id[r]);
	for(int i=r;id[i]==rid;i--){
		sum[id[i]]+=((k-1)*a[i])%MOD;sum[id[i]]%=MOD;
		a[i]*=k;a[i]%=MOD;
	}
	return;
}
void Plus(int l,int r,int k){
	reset(id[l]);
	int lid=id[l],rid=id[r];
	for(int i=l;id[i]==lid;i++){
		a[i]+=k;a[i]%=MOD;
		sum[id[i]]+=k;sum[id[i]]%=MOD;
	}
	for(int i=lid+1;i<rid;i++){
		tgp[i]+=k;tgp[i]%=MOD;
		sum[i]+=(k*(ed[i]-st[i]+1)%MOD)%MOD;sum[i]%=MOD; 
	}
	reset(id[r]);
	for(int i=r;id[i]==rid;i--){
		a[i]+=k;a[i]%=MOD;
		sum[id[i]]+=k;sum[id[i]]%=MOD;
	}
	return;
}
int query(int l,int r){
	int lid=id[l],rid=id[r],ans=0;
	for(int i=l;id[i]==lid;i++){
		ans+=((a[i]*tga[lid])%MOD+tgp[lid]%MOD);
		ans%=MOD;
	}
	int ans1=ans;
	for(int i=lid+1;i<rid;i++){
		ans+=(sum[i])%MOD;
		ans%=MOD;
	}
	ans1=ans;
	for(int i=r;id[i]==rid;i--){
		ans+=((a[i]*tga[rid])%MOD+tgp[rid]%MOD);
		ans%=MOD;
	}
	return ans;
}
signed main(){
	n=read(),q=read(),MOD=read();
	sz=sqrt((long long)n);
	for(int i=1;i<=n;i++){
		a[i]=read();
		id[i]=(i-1)/sz+1,sum[id[i]]+=a[i],sum[id[i]]%=MOD;
	}
	for(int i=1;i<=id[n];i++){
		tga[i]=1;
		st[i]=(i-1)*sz+1,ed[i]=(i)*sz;
	}
	int opt,x,y,k;
	while(q--){
		opt=read();
		if(opt==1){
			x=read(),y=read(),k=read();
			And(x,y,k);
		}else if(opt==2){
			x=read(),y=read(),k=read();
			Plus(x,y,k);
		}else{
			x=read(),y=read();
			write(query(x,y)%MOD);
			puts("");
		}
	}
	return 0;
}