#include<iostream>
const int N=1e7+10;
const int INF=0x3f3f3f3f;
using namespace std;
int n,mod,a[N],bj[N],bc[N],d[N],m;
void pushup(int p)
{
	d[p]=d[p*2]+d[p*2+1];
	d[p]%=mod;
}
void pushdown(int p,int l,int r)
{
	int mid=(l+r)/2;
	if(bc[p])
	{
		d[p*2]*=bc[p];
		d[p*2+1]*=bc[p];
		bc[p*2]=bc[p];
		bc[p*2+1]=bc[p];
		bc[p]=0;
	}
	if(bj[p])
	{
		d[p*2]+=(mid-l+1)*bj[p];
		d[p*2+1]+=(r-mid)*bj[p];
		bj[p*2]=bj[p];
		bj[p*2+1]=bj[p];
		bj[p]=0;
	}
	d[p]%=mod;
	d[p*2]%=mod;
	d[p*2+1]%=mod;
}
void build(int start,int end,int p)
{
	if(start==end)
	{
		d[p]=a[start];
		return;
	}
	int mid=(end+start)/2;
	build(start,mid,p*2);
	build(mid+1,end,p*2+1);
	pushup(p);
}
void update(int left,int right,int start,int end,int value,int p)
{
	if(left<=start&&end<=right)
	{
		d[p]+=(end-start+1)*value;
		bj[p]+=value;
		d[p]%=mod;
		return; 
	}
	int mid=(start+end)/2;
	pushdown(p,start,end);
	if(left<=mid)
	{
		update(left,right,start,mid,value,p*2); 
	}
	if(right>mid)
	{
		update(left,right,mid+1,end,value,p*2+1);
	}
	pushup(p);
}
void updated(int left,int right,int start,int end,int value,int p)
{
	if(left<=start&&end<=right)
	{
		d[p]*=value;
		bc[p]+=value;
		d[p]%=mod;
		return; 
	}
	int mid=(start+end)/2;
	pushdown(p,start,end);
	if(left<=mid)
	{
		updated(left,right,start,mid,value,p*2); 
	}
	if(right>mid)
	{
		updated(left,right,mid+1,end,value,p*2+1);
	}
	pushup(p);
}
int getsum(int left,int right,int start,int end,int p)
{
	if(left<=start&&end<=right)
	{
		return d[p]; 
	}
	int mid=(start+end)/2;
	pushdown(p,start,end);
	int sum=0;
	if(left<=mid)
	{
		sum+=getsum(left,right,start,mid,p*2);
	}
	if(right>mid)
	{
		sum+=getsum(left,right,mid+1,end,p*2+1);
	}
	sum%=mod;
	return sum; 
}
int main()
{
	cin>>n>>mod;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		a[i]%=mod;
	}
	build(1,n,1);
	cin>>m;
	while(m--)
	{
		int opt,x,y,z;
		cin>>opt;
		if(opt==1)
		{
			cin>>x>>y>>z;
			updated(x,y,1,n,z,1);
		}
		else if(opt==2)
		{
			cin>>x>>y>>z;
			update(x,y,1,n,z,1);
		}
		else if(opt==3)
		{
			cin>>x>>y;
			cout<<getsum(x,y,1,n,1)<<endl;
		}
	}
	return 0;
}