#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
    puts("");
}
const int maxn=1e5+5;
int n,MOD,sum[maxn<<2],lazy[maxn<<2],mul[maxn<<2],a[maxn],q,op,l,r,c;
inline void pushdown(int id,int l,int r)
{
	int mid=l+r>>1;
	if(mul[id]!=1)
	{
		mul[id<<1]*=mul[id];
		mul[id<<1]%=MOD;
		mul[id<<1|1]*=mul[id];
		mul[id<<1|1]%=MOD;
		lazy[id<<1]*=mul[id];
		lazy[id<<1]%=MOD;
		lazy[id<<1|1]*=mul[id];
		lazy[id<<1|1]%=MOD;
		sum[id<<1]*=mul[id];
	    sum[id<<1]%=MOD;
	    sum[id<<1|1]*=mul[id];
	    sum[id<<1|1]%=MOD;
	}
	if(lazy[id])
	{
		sum[id<<1]+=lazy[id]*(mid-l+1);
	    sum[id<<1]%=MOD;
	    sum[id<<1|1]+=lazy[id]*(r-mid);
	    sum[id<<1|1]%=MOD;
	    lazy[id<<1]+=lazy[id];
	    lazy[id<<1]%=MOD;
	    lazy[id<<1|1]+=lazy[id];
	    lazy[id<<1|1]%=MOD;
	    lazy[id]=0;
	}
}
inline void pushup(int id)
{
	sum[id]=(sum[id<<1]+sum[id<<1|1])%MOD;
	return;
}
inline void build(int id,int l,int r)
{
	mul[id]=1;
	if(l==r)
	{
		sum[id]=a[l];
		return;
	}
	int mid=l+r>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	pushup(id);
}
inline void cheng(int id,int l,int r,int x,int y,int v)
{
	if(x<=l&&r<=y)
	{
		mul[id]*=v;
		mul[id]%=MOD;
		lazy[id]*=v;
		lazy[id]%=MOD;
		sum[id]*=v;
		sum[id]%=MOD;
		return;
	}
	int mid=l+r>>1;
	pushdown(id,l,r);
	if(x<=mid)
	{
		cheng(id<<1,l,r,x,y,v);
	}
	if(y>mid)
	{
		cheng(id<<1|1,mid+1,r,x,y,v);
	}
	pushup(id);
}
inline void add(int id,int l,int r,int x,int y,int v)
{
	if(x<=l&&r<=y)
	{
		lazy[id]+=v;
		lazy[id]%=MOD;
		sum[id]+=(r-l+1)*v;
		sum[id]%=MOD; 
		return;
	}
	pushdown(id,l,r);
	int mid=l+r>>1;
	if(x<=mid)
	{
		add(id<<1,l,mid,x,y,v);
	}
	if(y>mid)
	{
		add(id<<1,mid+1,r,x,y,v);
	}
	pushup(id);
}
inline int query(int id,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)
	{
		return sum[id];
	}
	pushdown(id,l,r);
	int ans=0,mid=l+r>>1;
	if(x<=mid)
	{
		ans+=query(id<<1,l,mid,x,y);
	}
	ans%=MOD;
	if(y>mid)
	{
		ans+=query(id<<1|1,mid+1,r,x,y);
	}
	ans%=MOD;
	return ans;
}
int ans[100001],t=1;
signed main()
{
	n=read();
	MOD=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
	}
	build(1,1,n);
	q=read();
	while(q--)
	{
		op=read();
		if(op==1)
		{
			l=read();
			r=read();
			c=read();
			add(1,1,n,l,r,c);
		}
		if(op==2)
		{
			l=read();
			r=read();
			c=read();
			cheng(1,1,n,l,r,c);
		}
		if(op==3)
		{
			l=read();
			r=read();
			ans[t++]=query(1,1,n,l,r);
		}
	}
	for(int i=1;i<t;i++)
	{
		write(ans[i]);
	}
}