#include<iostream>
#include<cstdio>
#define N 100010
#define lc(x) ((x)<<1)
#define rc(x) ((x)<<1|1)
using namespace std;
typedef long long int ll;
int a[N];
int n,m,p;
struct node
{
	ll l,r,add,mul,val;
 }t[N<<2];
 
void build(int x,int l,int r)
{
	t[x].l=l;t[x].r=r;
	t[x].add=0;t[x].mul=1;
	if(l==r)
	{
		t[x].val=a[l]%p;
		return ;
	}
	int mid=(l+r)>>1;
	build(lc(x),l,mid);
	build(rc(x),mid+1,r);
	t[x].val=(t[lc(x)].val+t[rc(x)].val)%p;
}
void pushdown(int x)
{
	t[lc(x)].val=(t[lc(x)].val*t[x].mul+(t[lc(x)].r-t[lc(x)].l+1)*t[x].add)%p;
	t[rc(x)].val=(t[rc(x)].val*t[x].mul+(t[rc(x)].r-t[rc(x)].l+1)*t[x].add)%p;
	t[lc(x)].mul=(t[lc(x)].mul*t[x].mul)%p;
	t[rc(x)].mul=(t[rc(x)].mul*t[x].mul)%p;
	t[lc(x)].add=(t[lc(x)].add*t[x].mul+t[x].add)%p;
	t[rc(x)].add=(t[rc(x)].add*t[x].mul+t[x].add)%p;
	t[x].add=0;t[x].mul=1;
}
void mul(int x,int l,int r,int k)
{
//	printf("mul x:%d l:%d r:%d\n",x,t[x].l,t[x].r);
	if(t[x].l>=l&&t[x].r<=r)
	{
		t[x].val=(t[x].val*k)%p;
		t[x].add=(t[x].add*k)%p;
		t[x].mul=(t[x].mul*k)%p;
		return ;
	}
	pushdown(x); 
	int mid=(t[x].l+t[x].r)>>1;
	if(l<=mid) mul(lc(x),l,r,k);
	if(mid<r) mul(rc(x),l,r,k);
	t[x].val=(t[lc(x)].val+t[rc(x)].val)%p;
}
void add(int x,int l,int r,int k)
{
	if(t[x].l>=l&&t[x].r<=r)
	{
		t[x].val=(t[x].val+(t[x].r-t[x].l+1)*k)%p;
		t[x].add=(t[x].add+k)%p;
		return ;
	}
	int mid=(t[x].l+t[x].r)>>1;
	if(l<=mid) add(lc(x),l,r,k);
	if(mid<r) add(rc(x),l,r,k);
	t[x].val=(t[lc(x)].val+t[rc(x)].val)%p;
}
ll query(int x,int l,int r)
{
	if(t[x].l>=l&&t[x].r<=r)
	{
		return t[x].val;
	}
	pushdown(x);
	ll ans=0;
	int mid=(t[x].l+t[x].r)>>1;
	if(l<=mid) ans=(ans+query(lc(x),l,r))%p;
	if(mid<r) ans=(ans+query(rc(x),l,r))%p;
	return ans;
}
int main()
{
	cin>>n>>p;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	cin>>m;
	
	for(int i=1;i<=m;i++)
	{
	    int c,x,y,z;
	    cin>>c>>x>>y;
	    if(c==1)
	    {
	    	cin>>z;
	    	mul(1,x,y,z);
		}
		else if(c==2)
		{
			cin>>z;
			add(1,x,y,z);
		}
		else
		{
			ll ans=query(1,x,y);
			cout<<ans<<endl;
		}
	}
	return 0;
 }