输出20 27

#include <iostream> 
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define MAXN 50500 
using namespace std;
int n,m,p,a[MAXN],w[MAXN*4],mul[MAXN*4],add[MAXN*4];
void pushup(const int u)
{
	w[u]=(w[u*2]+w[u*2+1])%p;
}
bool InRange(int L,int R,int l,int r)
{
	return (l<=R) && (L<=l);
}
bool OutofRange(int L,int R,int l,int r)
{
	return (L>r) || (R<l);
}
void build(const int u,int L,int R) 
{
	mul[u]=1;
	add[u]=0;
	if(L==R)
	{
		w[u]=a[L];
		return;
	}
	else
	{
		int M=(L+R)/2;
		build(u*2,L,M);
		build(u*2+1,M+1,R);
		pushup(u);
	}
	w[u]%=p;
}
void pushdown(const int u,int L,int R)
{
	int M=(L+R)/2;
	w[u*2]=(w[u*2]*mul[u]+add[u]*(M-L+1))%p;
	w[u*2+1]=(w[u*2+1]*mul[u]+add[u]*(R-M))%p;
	mul[u*2]=(mul[u*2]*mul[u])%p;
	mul[u*2+1]=(mul[u*2+1]*mul[u])%p;
	add[u*2]=(add[u*2]*mul[u]+add[u])%p;
	add[u*2+1]=(add[u*2+1]*mul[u]+add[u])%p;
	mul[u]=1;
	add[u]=0;
}
void update1(int u,int L,int R,int l,int r,long long k)
{
	if(InRange(L,R,l,r))
	{
		w[u]=(w[u]*k)%p;
		add[u]=(add[u]*k)%p;
		mul[u]=(mul[u]*k)%p;
		return;
	}
	else if(!OutofRange(L,R,l,r))
	{
		int M=(L+R)/2;
		pushdown(u,L,R);
		update1(u*2,L,M,l,r,k);
		update1(u*2+1,M+1,R,l,r,k);
		pushup(u);
	}
}
void update2(int u,int L,int R,int l,int r,long long k)
{
	if(InRange(L,R,l,r))
	{
		add[u]=(add[u]+k)%p;
        w[u]=(w[u]+k*(R-L+1))%p;
		return;
	}
	else if(!OutofRange(L,R,l,r))
	{
		int M=(L+R)/2;
		pushdown(u,L,R);
		update2(u*2,L,M,l,r,k);
		update2(u*2+1,M+1,R,l,r,k);
		pushup(u);
	}
}
long long query(int u,int L,int R,int l,int r)
{
	if(InRange(L,R,l,r))
		return w[u];
	else if(!OutofRange(L,R,l,r))
	{
		int M=(L+R)/2;
		pushdown(u,L,R);
		return (query(u*2,L,M,l,r)+query(u*2+1,M+1,R,l,r))%p;
	}
	else
		return 0;
}
int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> m >> p;
	for(int i=1;i<=n;i++)
		cin >> a[i];
	build(1,1,n);
	while(m--) 
	{
		int op,x,y;
		long long k;
		cin >> op;
		if(op==1)
		{
			cin >> x >> y >> k;
			update1(1,1,n,x,y,k);
		}
		if(op==2)
		{
			cin >> x >> y >> k;
			update2(1,1,n,x,y,k);
		}
		if(op==3)
		{
			cin >> x >> y;
			cout << query(1,1,n,x,y) << endl;
		}
	}
	return 0;
}