【模板】线段树 2

#include<bits/stdc++.h>
using namespace std;
long long n,m,x,y,z,a[100005],k;
struct trees
{
	int l,r,num,adds,mu=1;
}t[400005];
void build(int l,int r,int g)
{
	t[g].adds=0,t[g].mu=1;
	t[g].l=l,t[g].r=r;
	if(l==r)
	{
		t[g].num=a[l]%k;
		return;
	}
	int mid=l+r>>1;
	build(l,mid,g*2);
	build(mid+1,r,g*2+1);
	t[g].num=(t[g*2].num+t[g*2+1].num)%k;
	return; 
}
void down(int g)
{
		
		t[g*2].num=( t[g*2].num*t[g].mu%k + (t[g*2].r-t[g*2].l+1)*t[g].adds%k )%k;
		t[g*2+1].num=( t[g*2+1].num*t[g].mu%k + (t[g*2+1].r-t[g*2].l+1)*t[g].adds%k )%k;
		
		t[g*2].mu*=t[g*2].mu*t[g].mu%k;
		t[g*2+1].mu*=t[g*2+1].mu*t[g].mu%k;
		
		t[g*2].adds=(t[g*2].adds*t[g].mu+t[g].adds)%k;
		t[g*2+1].adds=(t[g*2+1].adds*t[g].mu+t[g].adds)%k;
		
		t[g].mu=1;
		t[g].adds=0;
}
void mod(int l,int r,int num,int g)
{
	if(t[g].l>r||t[g].r<l)
	  return;
	if(t[g].l>=l&&t[g].r<=r)
	{
		t[g].mu=t[g].mu*num%k;
		t[g].num*=num;
		t[g].num%=k;
		return;
	}
	down(g);
	mod(l,r,num,g*2);
	mod(l,r,num,g*2+1);
	t[g].num=(t[g*2].num+t[g*2+1].num)%k;
	return;
}
void add(int l,int r,int num,int g)
{
	if(t[g].l>r||t[g].r<l)
	  return;
	if(t[g].l>=l&&t[g].r<=r)
	{
		t[g].adds=(t[g].adds+num)%k;
		t[g].num=(t[g].num+(t[g].r-t[g].l+1)*num)%k;
		t[g].num%=k;
		return;
	}
	down(g);
	add(l,r,num,g*2);
	add(l,r,num,g*2+1);
	t[g].num=t[g*2].num+t[g*2+1].num;
	t[g].num%=k;
	return;
}
int ask(int l,int r,int g)
{
	if(t[g].l>r||t[g].r<l)
	  return 0;
	if(t[g].l>=l&&t[g].r<=r)
	{
		//cout<<t[g].l<<' '<<t[g].r<<' '<<t[g].num%k<<'\n';
		return t[g].num%k;
	}
	int ans=(ask(l,r,g*2)+ask(l,r,g*2+1))%k;
    //cout<<t[g].l<<' '<<t[g].r<<' '<<ans<<'\n';
	return ans;
}
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=n;++i)
	  cin>>a[i];
	build(1,n,1);
	while(m--)
	{
		cin>>x;
		if(x==1)
		{
			cin>>x>>y>>z;
			mod(x,y,z,1);
		}else
		    if(x==2)
		    {
		    	cin>>x>>y>>z;
		    	add(x,y,z,1);
			}else
			{
				cin>>x>>y;
				cout<<ask(x,y,1)%k<<'\n';
			}
	}
}