https://www.luogu.com.cn/problem/P3373

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node
{
	int l,r,pre,add,mul;
};
node t[100010];
int a[100010];
int n,q,m;

void build(int l,int r,int u)
{
	t[u].l=l,t[u].r=r;
	if(l==r) 
	{
		t[u].pre=a[l];
		return;
	}
	int mid=l+r>>1;
	build(l,mid,u*2);
	build(mid+1,r,u*2+1);
	t[u].pre=t[2*u].pre+t[2*u+1].pre;
}
void spread(int p)
{
	if(t[p].mul>0)
	{
		t[p*2].pre+=(t[p*2].pre*(t[p].mul-1)%m);
		t[p*2+1].pre+=(t[p*2+1].pre*(t[p].mul-1)%m);
		t[p*2].mul+=t[p].mul;
		t[p*2+1].mul+=t[p].mul;
		t[p].mul=0;
	}
	if(t[p].add>0)
	{
		t[p*2].pre+=(t[p*2].r-t[p*2].l+1)*t[p].add%m;
		t[p*2+1].pre+=(t[p*2+1].r-t[p*2+1].l+1)*t[p].add%m;
		t[p*2+1].add+=t[p].add;
		t[p*2].add+=t[p].add;
		t[p].add=0;
	}
}
void change(int u,int l,int r,int z,int flag)
{
	if(t[u].l<=l && t[u].r>=r)
	{
		if(flag==1) t[u].pre+=z*(t[u].r-t[u].l+1)%m,t[u].add+=z;
		else t[u].pre+=t[u].pre*(z-1)%m,t[u].mul+=z;
		return;
	}
	spread(u);
	int mid=t[u].l+t[u].r>>1;
	if(l<=mid) change(u*2,l,r,z,flag);
	if(r>mid) change(u*2+1,l,r,z,flag);
}

int ask(int u,int x,int y)
{
	if(x<=t[u].l && y>=t[u].r) return t[u].pre;
	int ans=0;
	int mid=t[u].l+t[u].r>>1;
	if(x<=mid) ans+=ask(u*2,x,y)%m;
	if(y>mid) ans+=ask(u*2+1,x,y)%m;
	return ans;
}
signed main()
{
	scanf("%lld%lld%lld",&n,&q,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,n,1);
	while(q--)
	{
		int op,x,y,z;
		scanf("%lld",&op);
		if(op==1)
		{
			scanf("%lld%lld%lld",&x,&y,&z);
			change(1,x,y,z,1);
		}
		else if(op==2)
		{
			scanf("%lld%lld%lld",&x,&y,&z);
			change(1,x,y,z,2);
		}
		else 
		{
			scanf("%lld%lld",&x,&y);
			cout<<ask(1,x,y)%m<<endl;
		}
	}
}