#include<bits/stdc++.h>
using namespace std;
struct setree{
    long long l,r;
    long long sum,add1,add2;
    #define  l(x)  tree[x].l
    #define  r(x)  tree[x].r
    #define  sum(x)  tree[x].sum
    #define  add1(x)  tree[x].add1
    #define  add2(x)  tree[x].add2
 } tree[10000000];
long long a[10000001],n,m,s;
void build(int p,int l,int r)
{
    l(p)=l;r(p)=r;
    add2(p)=1;//乘法标记 
    if(l==r){  sum(p)=a[l]%s;return ;}
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build (p*2+1,mid+1,r);
    sum(p)=(sum(p*2)+sum(p*2+1))%s;
}
void spread(int p,int s)
{
    if(add2(p)!=1)
    {
        add2(p*2)=add2(p)%s*add2(p*2)%s;
        add2(p*2+1)=add2(p)%s*add2(p*2+1)%s;
        add1(p*2)=add2(p)%s*add1(p*2)%s;
        add1(p*2+1)=add2(p)%s*add1(p*2+1)%s;
        sum(p*2)=add2(p)%s*sum(p*2)%s;
        sum(p*2+1)=add2(p)%s*sum(p*2+1)%s;
        add2(p)=1;
    }
    if(add1(p))
    {
        add1(p*2)=add1(p*2)%s+add1(p)%s;
        add1(p*2+1)=add1(p*2+1)%s+add1(p)%s;
        sum(p*2)+=add1(p)*(r(p*2)%s-l(p*2)+1%s)%s;
        sum(p*2+1)+=add1(p)*(r(p*2+1)%s-l(p*2+1)+1%s)%s;
        add1(p)=0;
    }
}
void change1(int p,int l,int r,int d,int s)
{
    if(l<=l(p)&&r>=r(p))
    {
        sum(p)=(sum(p)%s+d*(r(p)-l(p)+1)%s)%s;
        add1(p)=(add1(p)%s+d%s)%s;
        return;
    }
    spread(p,s);
    int mid=(l(p)+r(p))%s/2;
    if(l<=mid)change1(p*2,l,r,d,s);
    if(r>mid)change1(p*2+1,l,r,d,s);
    sum(p)=(sum(p*2)+sum(p*2+1))%s;
}
void change2(int p,int l,int r,int d,int s)
{
    if(l<=l(p)&&r>=r(p))
    {
        sum(p)=(sum(p)*d)%s;
        add2(p)=(add2(p)*d)%s;
        add1(p)=(add1(p)*d)%s;
        return ;
    }
    spread(p,s);
    int mid=(l(p)+r(p))%s/2;
    if(l<=mid)change2(p*2,l,r,d,s);
    if(r>mid)change2(p*2+1,l,r,d,s);
    sum(p)=(sum(p*2)+sum(p*2+1))%s;
}
long long ask(int p,int l,int r,int s)
{
    if(l<=l(p)&&r>=r(p))
    {
        return sum(p);
    }

        spread(p,s);
        int mid=(l(p)+r(p))/2;
        long long val=0;
        if(l<=mid)val+=ask(p*2,l,r,s)%s;
        if(r>mid)val+=ask(p*2+1,l,r,s)%s;
        return val%s;

}
int main()
{
    long long b,c,d,k;
    cin>>n>>s;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build (1,1,n);
    cin>>m;
    while(m--)
    {
        cin>>b;
        if(b==3)
        {
            scanf("%d%d",&c,&d);
            cout<<ask(1,c,d,s)<<'\n';
        }
        if(b==1)
        {scanf("%d%d%d",&c,&d,&k);
            change2(1,c,d,k,s);
        }
        if(b==2)
        {scanf("%d%d%d",&c,&d,&k);
            change1(1,c,d,k,s);
        }
    }
    return 0;
}