https://www.luogu.com.cn/record/171379021

#include<bits/stdc++.h>
#define int long long
#define mid ((ll+rr)/2)
using namespace std;
const int N=500010;
int n,q,m,a[N],nd=0,sz[N*2],lc[N*2],rc[N*2],sm[N*2],lazyadd[N*2],lazymul[N*2];
void update(int s)
{
	sm[s]=((sm[lc[s]]%m)+(sm[rc[s]]%m))%m;
}
void multagadd(int s,int k)
{
	lazymul[s]*=k;
	lazymul[s]%=m;
	for (int i=1;i<=sz[s];i++)
	{
		sm[s]*=k;
		sm[s]%=m;
	}
}
void addtagadd(int s,int k)
{
	lazyadd[s]+=k;
	lazyadd[s]%=m;
	sm[s]+=((sz[s]%m)*(k%m))%m;
	sm[s]%=m;
}
void pushdown(int s)
{
	if (lc[s])
	{
		if (lazymul[s])
		{
			multagadd(lc[s],lazymul[s]);
			multagadd(rc[s],lazymul[s]);
			lazymul[s]=1;
		}
		if (lazyadd[s])
		{
			addtagadd(lc[s],lazyadd[s]);
			addtagadd(rc[s],lazyadd[s]);
			lazyadd[s]=0;
		}
	}
}
void Build(int s,int ll,int rr)
{
	if (ll==rr)
	{
		sm[s]+=a[ll];
		sm[s]%=m;
		sz[s]=1;
		return ;
	}
	Build(lc[s]=++nd,ll,mid);
	Build(rc[s]=++nd,mid+1,rr);
	update(s);
	sz[s]=sz[lc[s]]+sz[rc[s]];
}
void Mul(int s,int ll,int rr,int l,int r,int k)
{
	if (l>rr||r<ll) return ;
	if (l<=ll&&rr<=r)
	{
		multagadd(s,k);
		return ;
	}
	pushdown(s);
	Mul(lc[s],ll,mid,l,r,k);
	Mul(rc[s],mid+1,rr,l,r,k);
	update(s);
}
void Add(int s,int ll,int rr,int l,int r,int k)
{
	if (l>rr||r<ll) return ;
	if (l<=ll&&rr<=r)
	{
		addtagadd(s,k);
		return ;
	}
	pushdown(s);
	Add(lc[s],ll,mid,l,r,k);
	Add(rc[s],mid+1,rr,l,r,k);
	update(s);
}
int Query(int s,int ll,int rr,int l,int r)
{
	if (l>rr||r<ll) return 0;
	if (l<=ll&&rr<=r) return sm[s]%m;
	pushdown(s);
	return (Query(lc[s],ll,mid,l,r)%m+Query(rc[s],mid+1,rr,l,r)%m)%m;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q>>m;
	for (int i=1;i<=500005;i++) lazymul[i]=1;
	for (int i=1;i<=n;i++) cin>>a[i];
	Build(++nd,1,n);
	while (q--)
	{
		int op,x,y,k;
		cin>>op>>x>>y;
		if (op==1)
		{
			cin>>k;
			Mul(1,1,n,x,y,k);
		}
		else if (op==2)
		{
			cin>>k;
			Add(1,1,n,x,y,k);
		}
		else
		{
			cout<<Query(1,1,n,x,y)<<'\n';
		}
	}
	return 0;
}