```
#include<bits/stdc++.h>
using namespace std;
struct node{
	long long l,r,sum,mul,add;
}t[400005];
long long mod;
long long L(long long x){return x<<1;}
long long R(long long x){return x<<1|1;}
long long a[400005],n,m;
void update(long long x){
	t[x].sum=(t[L(x)].sum+t[R(x)].sum)%mod;
	return;
}
void push_down(long long x){
	t[L(x)].sum=(t[L(x)].sum*t[x].mul+t[x].add*(t[L(x)].r-t[L(x)].l+1))%mod;
	t[R(x)].sum=(t[R(x)].sum*t[x].mul+t[x].add*(t[R(x)].r-t[R(x)].l+1))%mod;
	t[L(x)].mul=(t[L(x)].mul*t[x].mul)%mod;
	t[R(x)].mul=(t[R(x)].mul*t[x].mul)%mod;
	t[L(x)].add=(t[L(x)].add*t[x].mul+t[x].add)%mod;
	t[R(x)].add=(t[R(x)].add*t[x].mul+t[x].add)%mod;
	t[x].add=0;
	t[x].mul=1;
	return;
}
void build(long long x,long long l,long long r){
	t[x].l=l;
	t[x].r=r;
	t[x].mul=1;
	if(t[x].l==t[x].r){
		t[x].sum=a[l]%mod;
		return;
	}
	long long mid=(t[x].l+t[x].r)>>1;
	build(L(x),l,mid);
	build(R(x),mid+1,r);
	update(x);
	return;
}
void modifyadd(long long x,long long l,long long r,long long add){
	if(l<=t[x].l&&r>=t[x].r){
		t[x].sum+=(t[x].r-t[x].l+1)*add;
		t[x].sum%=mod;
		t[x].add+=add;
		t[x].add%=mod;
		return;
	}
	push_down(x);
	long long mid=(t[x].l+t[x].r)>>1;
	if(l<=mid)modifyadd(L(x),l,r,add);
	if(mid+1<=r)modifyadd(R(x),l,r,add);
	update(x);
	return;
}
void modifymul(long long x,long long l,long long r,long long add){
	if(l<=t[x].l&&r>=t[x].r){
		t[x].add*=add;
		t[x].add%=mod;
		t[x].sum*=add;
		t[x].sum%=mod;
		t[x].mul*=add;
		t[x].mul%=mod;
		return;
	}
	push_down(x);
	long long mid=(t[x].l+t[x].r)>>1;
	if(l<=mid)modifymul(L(x),l,r,add);
	if(mid+1<=r)modifymul(R(x),l,r,add);
	update(x);
	return;
}
long long query(long long x,long long l,long long r){
	if(l<=t[x].l&&r>=t[x].r){
		return t[x].sum;
	}
	push_down(x);
	long long mid=(t[x].l+t[x].r)>>1;
	long long ans=0;
	if(l<=mid)ans+=query(L(x),l,r)%mod;
	if(mid+1<=r)ans+=query(R(x),l,r)%mod;
	return ans%mod;
}
int main(){
	int x,y,k;
	cin>>n>>m>>mod;
	for(long long i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	long long opt;
	for(long long i=1;i<=m;i++){
		cin>>opt;
		if(opt==1){
			cin>>x>>y>>k;
			modifymul(1,x,y,k);
		}else if(opt==2){
			cin>>x>>y>>k;
			modifyadd(1,x,y,k);
		}else{
			cin>>x>>y;
			cout<<query(1,x,y)<<endl;
		}
	}
	return 0;
}
```