#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int mod;
int qj[maxn];
struct ll{
	bool mo;
	int k;
};
struct xds{
	int left;
	int right;
	int ans;
	deque <ll> lazy;
};
xds tr[4*maxn];
void build(int le,int ri,int x)
{
	tr[x].left=le;
	tr[x].right=ri;
	if(le==ri)
	{
		tr[x].ans=qj[le]%mod;
		return;
	}
	int mid=(le+ri)/2;
	build(le,mid,2*x);
	build(mid+1,ri,2*x+1);
	tr[x].ans=(tr[2*x].ans+tr[2*x+1].ans)%mod;
	return;
}
void jla(int rt,ll k)
{
	
	if(tr[rt].left==tr[rt].right) return;
	if(tr[rt].lazy.empty())
	{
		tr[rt].lazy.push_back(k);
		return;
	}
	ll t=tr[rt].lazy.back();
	if(t.mo==k.mo)
	{
		tr[rt].lazy.pop_back();
		if(t.mo==1) t.k=t.k*k.k%mod;
		else t.k=(t.k+k.k)%mod;
		tr[rt].lazy.push_back(t);
	}
	else tr[rt].lazy.push_back(k);
}
void pus(int rt)
{
	int le=rt*2,ri=rt*2+1;
	while(!tr[rt].lazy.empty())
	{
		ll k=tr[rt].lazy.front();tr[rt].lazy.pop_front();
		jla(le,k),jla(ri,k);
		if(k.mo==0) tr[le].ans=(tr[le].ans+k.k*(tr[le].right-tr[le].left+1))%mod;
		else tr[le].ans=(int)((long long)tr[le].ans*k.k%mod);
		if(k.mo==0) tr[ri].ans=(tr[ri].ans+k.k*(tr[ri].right-tr[ri].left+1))%mod;
		else tr[ri].ans=(int)((long long)tr[ri].ans*k.k%mod);
	}
}
void xg(int x,int y,int k,int rt,bool mo)
{
	if(x>y) return;
	if(x<=tr[rt].left&&tr[rt].right<=y)
	{
		ll t;t.k=k,t.mo=mo;
		jla(rt,t);
		if(mo==0) tr[rt].ans=(tr[rt].ans+k*(tr[rt].right-tr[rt].left+1))%mod;
		else tr[rt].ans=(int)((long long)tr[rt].ans*k%mod);
		return;
	}
	pus(rt);
	int mid=(tr[rt].left+tr[rt].right)/2;
	if(x<=mid)
		xg(x,y,k,2*rt,mo);
	if(y>mid)
		xg(x,y,k,2*rt+1,mo);
	tr[rt].ans=tr[2*rt].ans+tr[2*rt+1].ans;
	return;
}
int js(int x,int y,int rt)
{
	int ans=0;
	if(x>y) return 0;
	if(x<=tr[rt].left&&tr[rt].right<=y)
	{
		return tr[rt].ans;
	}
	pus(rt);
	int mid=(tr[rt].left+tr[rt].right)/2;
	if(x<=mid)
		ans=(ans+js(x,y,2*rt))%mod;
	if(y>mid)
		ans=(ans+js(x,y,2*rt+1))%mod;
	return ans;
}
signed main()
{
	int n,m;
	scanf("%d%d%d",&n,&m,&mod);
	for(int i=1;i<=n;i++)
		scanf("%d",&qj[i]);
	build(1,n,1);
	for(int ii=1;ii<=m;ii++)
	{
		int cz;
		scanf("%d",&cz);
		if(cz==1)
		{
			int x,y,k;
			scanf("%d%d%d",&x,&y,&k);
			xg(x,y,k,1,1);
		}
		if(cz==2)
		{
			int x,y,k;
			scanf("%d%d%d",&x,&y,&k);
			xg(x,y,k,1,0);
		}
		if(cz==3)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			printf("%d\n",js(x,y,1));
		}
	}
	return 0;
}

之前的队列为了优化已经用双向队列缩小了,但是还是MLE,求教