rt

#include<bits/stdc++.h>
#define ls (x<<1)
#define rs (x<<1|1)
#define re register
#define il inline 
#define ll long long
#define N 400005
using namespace std;
il int read()
{
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
il void write(ll x)
{
	if(x<0) {x=~(x-1); putchar('-');}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
struct hh
{
	ll add,mul;
}tag[N];
ll n,m,mod,f[N],sum[N];
il void take(int x)
{
	sum[x]=sum[ls]+sum[rs];sum[x]%=mod;
}
il void down(ll x,ll l,ll r)
{
	ll mid=(l+r)>>1;
	
	sum[ls]*=tag[x].mul;sum[ls]%=mod;
	sum[ls]+=tag[x].add*(mid-l+1)%mod;sum[ls]%=mod;
	sum[rs]*=tag[x].mul;sum[rs]%=mod;
	sum[rs]+=tag[x].add*(r-mid)%mod;sum[rs]%=mod;
	
	tag[ls].mul*=tag[x].mul;tag[ls].mul%=mod;
	tag[rs].mul*=tag[x].mul;tag[rs].mul%=mod;
	
	tag[ls].add*=tag[x].mul;tag[ls].add%=mod;
	tag[ls].add+=tag[x].add;tag[ls].add%=mod;
	tag[rs].add*=tag[x].mul;tag[rs].add%=mod;
	tag[rs].add+=tag[x].add;tag[rs].add%=mod;
	
	tag[x].add=0;tag[x].mul=1;
}
il void build(ll x,ll l,ll r)
{
	tag[x].mul=1;
	if(l==r){sum[x]=f[l];return;}
	ll mid=(l+r)>>1;
	build(ls,l,mid);build(rs,mid+1,r);
	take(x);
}
il ll query(ll A,ll B,ll x,ll l,ll r)
{
	if(B<l||r<A) return 0;
	if(A<=l&&r<=B) return sum[x];
	ll mid=(l+r)>>1,s1,s2;
	down(x,l,r);
	s1=query(A,B,ls,l,mid);
	s2=query(A,B,rs,mid+1,r);
	return (s1+s2)%mod;
}
il void change1(ll A,ll B,ll x,ll l,ll r,ll v)
{
	if(B<l||r<A) return;
	if(A<=l&&r<=B)
	{
		tag[x].add+=v;
		sum[x]+=v*(r-l+1)%mod;
		tag[x].add%=mod;
		sum[x]%=mod;
		return;
	}
	ll mid=(l+r)>>1;down(x,l,r);
	change1(A,B,ls,l,mid,v);
	change1(A,B,rs,mid+1,r,v);
	take(x);
}
il void change2(ll A,ll B,ll x,ll l,ll r,ll v)
{
	if(B<l||r<A) return;
	if(A<=l&&r<=B)
	{
		sum[x]*=v;
		tag[x].mul*=v;
		tag[x].add*=v;
		sum[x]%=mod;
		tag[x].mul%=mod;
		tag[x].add%=mod;
		return;
	}
	ll mid=(l+r)>>1;down(x,l,r);
	change2(A,B,ls,l,mid,v);
	change2(A,B,rs,mid+1,r,v);
	take(x);
}
int main()
{
	n=read(),mod=read();
	for(re ll i=1;i<=n;i++) f[i]=read()%mod;
	build(1,1,n);
	m=read();
	for(re ll x,y,z,q,i=1;i<=m;i++)
	{
		q=read();
		if(q==1) x=read(),y=read(),z=read(),change2(x,y,1,1,n,z);
		else if(q==2) x=read(),y=read(),z=read(),change2(x,y,1,1,n,z);
		else if(q==3) x=read(),y=read(),write(query(x,y,1,1,n)),puts("");
	}
	return 0;
}