#include<bits/stdc++.h>
using namespace std;
int n,m,st[400001],a[100001],lazy[400001],lazy2[400001],p,op,x,y,z;
void pushdown(int rt,int l,int r) 
{
	if((lazy[rt]||lazy2[rt]>1))
	{
		int mid=(l+r)/2;
		st[rt*2]=(st[rt*2]*lazy2[rt]+lazy[rt]*(mid-l+1))%p;
		st[rt*2+1]=(st[rt*2+1]*lazy2[rt]+lazy[rt]*(r-mid))%p;
		lazy2[rt*2]=(lazy2[rt*2]*lazy2[rt])%p;
		lazy2[rt*2+1]=(lazy2[rt*2+1]*lazy2[rt])%p;
		lazy[rt*2]=(lazy2[rt]*lazy[rt*2]+lazy[rt])%p;
		lazy[2*rt+1]=(lazy2[rt]*lazy[rt*2+1]+lazy[rt])%p;
		lazy[rt]=0;
		lazy2[rt]=1;
	}
}
int creat(int rt,int l,int r)
{
	if(l==r)return st[rt]=a[l];
	int mid=(l+r)/2;
	st[rt]=creat(2*rt,l,mid)+creat(2*rt+1,mid+1,r);
	return st[rt];
}
int Find(int rt,int l,int r,int s,int e)
{
	int ans=0,mid=(l+r)/2;
	pushdown(rt,l,r);
	if(s<=l&&r<=e)return st[rt];
	if(s<=mid)ans+=Find(2*rt,l,mid,s,e);
	if(e>mid)ans+=Find(2*rt+1,mid+1,r,s,e);
	return ans;
}
void qujian(int rt,int l,int r,int s,int e,int x)
{
	if(s<=l&&r<=e){
		st[rt]+=(r-l+1)*x;
		lazy[rt]+=x; 
		return;
	}
	pushdown(rt,l,r);
	int mid=(l+r)/2;
	if(s<=mid)qujian(rt*2,l,mid,s,e,x);
	if(e>mid)qujian(rt*2+1,mid+1,r,s,e,x); 
	st[rt]=st[2*rt]+st[rt*2+1];
} 
void qujian2(int rt,int l,int r,int s,int e,int x)
{
	int mid=(l+r)>>1;
	if(s<=l&&r<=e){
		st[rt]*=x;
		lazy2[rt]*=x;
		lazy[rt]*=x;
		return;
	}
	pushdown(rt,l,r);
	if(s<=mid)qujian2(rt*2,l,mid,s,e,x);
	if(e>mid)qujian2(rt*2+1,mid+1,r,s,e,x);
	st[rt]=st[2*rt]+st[rt*2+1];
}
int main(){
	cin>>n>>p;
	for(int i=1;i<=n;i++)lazy2[i]=1;
	for(int i=1;i<=n;i++)cin>>a[i];
	creat(1,1,n);
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>z;
			if(z==1)continue;
			qujian2(1,1,n,x,y,z);
		}
		if(op==2)
		{
			cin>>x>>y>>z;
			qujian(1,1,n,x,y,z);
		}
		if(op==3)
		{
			cin>>x>>y;
			cout<<Find(1,1,n,x,y)%p<<endl;
		}
	}
	return 0;
}