7WA3AC

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
long long int a[N],n,nn;
inline long long int read() 
{
    long long int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
void write(long long int x) 
{
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}
struct node
{
	int l,r;
	long long int sum;
	long long int lazy=0,lazy1=1;
}t[4*N];
void pushup(int x)
{
	t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
}
void pushdown(int x)
{	if(t[x].lazy!=0||t[x].lazy1!=1)
{
	t[x*2].lazy1*=t[x].lazy1;
	t[x*2].lazy1%=nn;
	t[x*2+1].lazy1*=t[x].lazy1;	
	t[x*2+1].lazy1%=nn;
	t[x*2].lazy=(t[x].lazy+t[2*x].lazy*t[x].lazy1)%nn;
    t[x*2+1].lazy=(t[x].lazy+t[2*x+1].lazy*t[x].lazy1)%nn;
    t[x*2].sum=(t[2*x].sum*t[x].lazy1+t[x].lazy*(t[x*2].r-t[x*2].l+1)%nn)%nn;
	t[x*2+1].sum=(t[2*x+1].sum*t[x].lazy1+t[x].lazy*(t[x*2+1].r-t[x*2+1].l+1)%nn)%nn;
    t[x].lazy1=1;	
	t[x].lazy=0;
}

}
void build(int p,int l,int r)
{
	t[p].l=l;
	t[p].r=r;
	if(l==r)
	{
		t[p].sum=a[l]%nn;
		return;
	}
	long long int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	pushup(p);
}
void change(long long int p,long long int l,long long int r,long long int x)
{	
	if(l<=t[p].l&&t[p].r<=r)
	{	
		t[p].lazy+=x;
		t[p].sum=(t[p].sum+x*(t[p].r-t[p].l+1))%nn;
		return;
	}
	pushdown(p);
	long long int mid=t[p].l+t[p].r>>1;
	if(l<=mid)
	{
		change(p<<1,l,r,x);
	}
	if(mid<r)
	{
	change(p<<1|1,l,r,x);	
	}
	pushup(p);
	return;
}
void change1(long long int p,long long int l,long long int r,long long int x)
{	
	if(l<=t[p].l&&t[p].r<=r)
	{	t[p].lazy1*=x;	
		t[p].lazy*=x;
		t[p].sum*=x;
		t[p].sum%=nn;
		return;
	}
	pushdown(p);
	long long int mid=t[p].l+t[p].r>>1;
	if(l<=mid)
	{
		change1(p<<1,l,r,x);
	}
	if(mid<r)
	{
	change1(p<<1|1,l,r,x);	
	}
	pushup(p);
	return;
}
long long int add(int p,int l,int r)
{	
	if(l<=t[p].l&&t[p].r<=r)
	{
		return t[p].sum;
	}
	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	long long int ret=0;
	if(l<=mid)
	{
		ret+=add(p<<1,l,r)%nn;
	}
	if(r>mid)
	{
		ret+=add(p<<1|1,l,r)%nn;
	}
	return ret;
}
int main()
{int m;
cin>>n>>m>>nn;
for(int i=1;i<=n;i++)
{
	a[i]=read();
}
build(1,1,n);
int k,b,c,d;
for(int j=1;j<=m;j++)
{
	k=read();
	if(k==1)
	{
		b=read();
		c=read();
		d=read();
		change1(1,b,c,d);
	}
	if(k==2)
	{
		b=read();
		c=read();
		d=read();
		change(1,b,c,d);		
	}
	if(k==3)
	{
		b=read();
		c=read();
		write(add(1,b,c));
		cout<<endl;
	}
}
	return 0;
}