#include<bits/stdc++.h>
using namespace std;
#define long long ll
ll a[2000001],n,m,p,i,pd,x,y,k;
struct student
{
    ll l,r,sum,lazyj,lazyc;
}tree[2000001];
ll lson(ll x)
{
    return x*2;
}
ll rson(ll x)
{
    return x*2+1;
}
void pushup(ll rt)
{
    tree[rt].sum=(tree[lson(rt)].sum%p+tree[rson(rt)].sum%p)%p;
}
void build(ll rt,ll l,ll r)
{
    tree[rt].l=l;
    tree[rt].r=r;
    tree[rt].lazyc=1;
    if(l==r)
    {
        tree[rt].sum=a[l]%p;
        return;
    }
    ll mid=(l+r)/2;
    build(lson(rt),l,mid);
    build(rson(rt),mid+1,r);
    pushup(rt);
}
void pushdown(ll rt)
{
    tree[lson(rt)].sum=(tree[lson(rt)].sum*tree[rt].lazyc+tree[rt].lazyj*(tree[lson(rt)].r-tree[lson(rt)].l+1))%p;
    tree[rson(rt)].sum=(tree[rson(rt)].sum*tree[rt].lazyc+tree[rt].lazyj*(tree[rson(rt)].r-tree[rson(rt)].l+1))%p;
    tree[lson(rt)].lazyc=(tree[rt].lazyc*tree[lson(rt)].lazyc)%p;
    tree[rson(rt)].lazyc=(tree[rt].lazyc*tree[rson(rt)].lazyc)%p;
    tree[lson(rt)].lazyj=(tree[rt].lazyc*tree[lson(rt)].lazyj+tree[rt].lazyj)%p;
    tree[rson(rt)].lazyj=(tree[rt].lazyc*tree[rson(rt)].lazyj+tree[rt].lazyj%p)%p;
    tree[rt].lazyj=0;
    tree[rt].lazyc=1;
}
void updatej(ll rt,ll l,ll r,ll val)
{
    if(l<=tree[rt].l&&tree[rt].r<=r)
    {
    	tree[rt].lazyj=(tree[rt].lazyj+val)%p;
        tree[rt].sum=(tree[rt].sum%p+val*(tree[rt].r-tree[rt].l+1))%p;
        return;
    }
    pushdown(rt);
    ll mid=(tree[rt].l+tree[rt].r)/2;
    if(l<=mid)
    {
        updatej(lson(rt),l,r,val);
    }
    if(mid<r)
    {
        updatej(rson(rt),l,r,val);
    }
	pushup(rt);
}
void updatec(ll rt,ll l,ll r,ll val)
{
    if(l<=tree[rt].l&&tree[rt].r<=r)
    {
        tree[rt].lazyj*=val;
        tree[rt].lazyj%=p;
        tree[rt].lazyc*=val;
        tree[rt].lazyj%=p;
        tree[rt].sum*=val;
        tree[rt].sum%=p;
        return;
    }
    pushdown(rt);
    ll mid=(tree[rt].l+tree[rt].r)/2;
    if(l<=mid)
    {
        updatec(lson(rt),l,r,val);
    }
    if(mid<r)
    {
        updatec(rson(rt),l,r,val);
    }
    pushup(rt);
}
ll query(ll rt,ll l,ll r)
{
    if(l<=tree[rt].l&&tree[rt].r<=r)
    {
        return tree[rt].sum%p;
    }
    pushdown(rt);
    ll mid=(tree[rt].l+tree[rt].r)/2,ans=0;
    if(l<=mid)
    {
        ans=(ans%p+query(lson(rt),l,r)%p)%p;
    }
    if(mid<r)
    {
        ans=(ans%p+query(rson(rt),l,r)%p)%p;
    }
    return ans%p;
}
int main()
{
	cin>>n>>p;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	cin>>m; 
	for(i=1;i<=m;i++)
	{
		cin>>pd;
		if(pd==1)
		{
			cin>>x>>y>>k;
			updatec(1,x,y,k);
		}
		if(pd==2)
		{
			cin>>x>>y>>k;
			updatej(1,x,y,k);
		}
		if(pd==3)
		{
			cin>>x>>y;
			cout<<query(1,x,y)%p<<endl;
		}
	}
    return 0;
}