线段树2

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,q,m;
int a[N];
int lazy_tag_add[4*N];
int lazy_tag_mul[4*N];
int tree[4*N];
int ls(int p)
{
	return p << 1;
}
int rs(int p)
{
	return p << 1 | 1;
}
void push_up(int p)
{
	tree[p]=tree[ls(p)]+tree[rs(p)];
	tree[p]%=m;
}
void build(int p,int l,int r)
{
	lazy_tag_add[p]=0;
	lazy_tag_mul[p]=1;
	if(l==r)
	{
		tree[p]=a[l];
		return;
	}
	int mid=(l+r) >> 1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	push_up(p);
}
void mul_tag(int p,int l,int r,int k)
{
	lazy_tag_mul[p]*=k;
	lazy_tag_mul[p]%=m;
	lazy_tag_add[p]*=k;
	lazy_tag_add[p]%=m;
	tree[p]*=k;
	tree[p]%=m;
}
void add_tag(int p,int l,int r,int k)
{
	lazy_tag_add[p]+=k;
	lazy_tag_add[p]%=m;
	tree[p]+=k*(r-l+1);
	tree[p]%=m;
}
void push_down_mul(int p,int l,int r)
{
	if(lazy_tag_mul[p]!=1)
	{
		int mid=(l+r) >> 1;
		mul_tag(ls(p),l,mid,lazy_tag_mul[p]);
		mul_tag(rs(p),mid+1,r,lazy_tag_mul[p]);
		lazy_tag_mul[p]=1;
	}
}
void push_down_add(int p,int l,int r)
{
	if(lazy_tag_add[p]!=0)
	{
		int mid=(l+r) >> 1;
		add_tag(ls(p),l,mid,lazy_tag_add[p]);
		add_tag(rs(p),mid+1,r,lazy_tag_add[p]);
		lazy_tag_add[p]=0;
	}
}
void push_down(int p,int l,int r)
{
	push_down_add(p,l,r);
	push_down_mul(p,l,r);
}
void updata_mul(int L,int R,int p,int l,int r,int k)
{
	if(L<=l && R>=r)
	{
		mul_tag(p,l,r,k);
		return;
	}
	push_down(p,l,r);
	int mid=(l+r) >> 1;
	if(L<=mid)updata_mul(L,R,ls(p),l,mid,k);
	if(R>mid)updata_mul(L,R,rs(p),mid+1,r,k);
	push_up(p);
}
void updata_add(int L,int R,int p,int l,int r,int k)
{
	if(L<=l && R>=r)
	{
		add_tag(p,l,r,k);
		return;
	}
	push_down(p,l,r);
	int mid=(l+r) >> 1;
	if(L<=mid)updata_add(L,R,ls(p),l,mid,k);
	if(R>mid)updata_add(L,R,rs(p),mid+1,r,k);
	push_up(p);
}
int query(int L,int R,int p,int l,int r)
{
	if(L<=l && R>=r)
	{
		return tree[p];
	}
	push_down(p,l,r);
	int sum=0;
	int mid=(l+r) >> 1;
	if(L<=mid)
	{
		sum+=query(L,R,ls(p),l,mid);
		sum%=m;
	}
	if(R>mid)
	{
		sum+=query(L,R,rs(p),mid+1,r);
		sum%=m;
	}
	return sum;
}
signed main()
{
	cin>>n>>q>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	while(q--)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int l,r,k;
			cin>>l>>r>>k;
			updata_mul(l,r,1,1,n,k);
		}
		else if(op==2)
		{
			int l,r,k;
			cin>>l>>r>>k;
			updata_add(l,r,1,1,n,k);
		}
		else 
		{
			int l,r;
			cin>>l>>r;
			cout<<query(l,r,1,1,n)<<endl;
		}
	}
	return 0;
}