#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,p,m;
ll ans;
struct tree
{
	int l,r;
	ll w,f1,f2;
}t[1200010];
inline void build(int k,int ll,int rr)
{
	t[k].l=ll;
	t[k].r=rr;
	t[k].f1=1;
	t[k].f2=0;
	if(ll==rr)
	{
		scanf("%lld",&t[k].w);
		//cout<<ll<<"  "<<rr<<"  "<<t[k].w<<endl;
		return;
	}
	int mid=(ll+rr)>>1;
	build(k<<1,ll,mid);
	build(k<<1|1,mid+1,rr);
	t[k].w=(t[k<<1].w+t[k<<1|1].w)%p;
}
inline void down(int k)
{
	t[k<<1].w=( t[k<<1].w*t[k].f1 + (t[k<<1].r-t[k<<1].l+1) *t[k].f2 )%p;
	t[k<<1|1].w=(t[k<<1|1].w*t[k].f1+ (t[k<<1|1].r-t[k<<1|1].l+1) *t[k].f2)%p;
	t[k<<1].f1=(t[k<<1].f1*t[k].f1)%p;
	t[k<<1|1].f1=(t[k<<1|1].f1*t[k].f1)%p;
	t[k<<1].f2=(t[k<<1].f2+t[k].f2)%p;
	t[k<<1|1].f2=(t[k<<1|1].f2+t[k].f2)%p;
	t[k].f1=1;t[k].f2=0;
}
inline void add1(int k,int a,int b,ll y)
{
	if(t[k].l>=a&&t[k].r<=b)
	{
		t[k].w=(t[k].w*y)%p;
		t[k].f1=(t[k].f1*y)%p;
		t[k].f2=(t[k].f2*y)%p;
		return ;
	}
	down(k);
	int mid=(t[k].l+t[k].r)>>1;
	if(mid>=a)add1(k<<1,a,b,y);
	if(mid<b)add1(k<<1|1,a,b,y);
	t[k].w=(t[k<<1].w+t[k<<1|1].w)%p;
}
inline void add2(int k,int a,int b,ll y)
{
	if(t[k].l>=a&&t[k].r<=b)
	{
		t[k].w=(t[k].w+(t[k].r-t[k].l+1)*y)%p;
		t[k].f2=(t[k].f2+y)%p;
		return ;
	}
	down(k);
	int mid=(t[k].l+t[k].r)>>1;
	if(mid>=a)add2(k<<1,a,b,y);
	if(mid<b)add2(k<<1|1,a,b,y);
	t[k].w=(t[k<<1].w+t[k<<1|1].w)%p;
}
inline void check(int k,int a,int b)
{
	if(t[k].l>=a&&t[k].r<=b)
	{
		//<<"查询到："<<t[k].w<<endl; 
		ans=(ans+t[k].w)%p;
		return ;
	}
	down(k);
	int mid=(t[k].l+t[k].r)>>1;
	if(mid>=a)check(k<<1,a,b);
	if(mid<b)check(k<<1|1,a,b);
}
int main()
{
	scanf("%d%d",&n,&p);
	build(1,1,n);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int g,a,b;
		ll y;
		scanf("%d",&g);
		if(g==1)
		{
			scanf("%d%d%lld",&a,&b,&y);
			add1(1,a,b,y);
		}
		else if(g==2)
		{
			scanf("%d%d%lld",&a,&b,&y);
			add2(1,a,b,y);
		}
		else
		{
			scanf("%d%d",&a,&b);
			ans=0;
			check(1,a,b);
			printf("%lld\n",ans);
		}
	}
}```