#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n;
ll mod,sum[N<<2],add[N<<2],mul[N<<2],w[N];
void pushup(int u){
    sum[u]=(sum[u<<1]+sum[u<<1|1])%mod;
}
void build(int l,int r,int u){
    if(l==r){
        sum[u]=w[l];
        add[u]=0;
        mul[u]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,u<<1);
    build(mid+1,r,u<<1|1);
    pushup(u);
}
void pushdown(int u,int len){
    if(add[u]!=0 || mul[u]!=1){
        int ls=u<<1,rs=u<<1|1;
        add[ls]=(add[ls]*mul[u]%mod+add[u])%mod;
        add[rs]=(add[rs]*mul[u]%mod+add[u])%mod;
        mul[ls]=((mul[ls]%mod)*(mul[u]%mod))%mod;
        mul[rs]=((mul[rs]%mod)*(mul[u]%mod))%mod;
        sum[ls]=((sum[ls]%mod)*(mul[u]%mod))%mod;
        sum[ls]=(sum[ls]+(len-(len>>1))*add[u]%mod)%mod;
        sum[rs]=((sum[rs]%mod)*(mul[u]%mod))%mod;
        sum[rs]=(sum[rs]+(len>>1)*add[u]%mod)%mod;
        add[u]=0;
        mul[u]=1;
    } 
}
void jia(int l,int r,ll v,int le,int ri,int u){
    if(l<=le && ri<=r){
        add[u]=(add[u]+v)%mod;
        sum[u]=(sum[u]+v*(ri-le+1)%mod)%mod;
        return;
    }
    pushdown(u,ri-le+1);
    int mid=(le+ri)>>1;
    if(l<=mid) jia(l,r,v,le,mid,u<<1);
    if(r>mid) jia(l,r,v,mid+1,ri,u<<1|1);
    pushup(u);
}
void cheng(int l,int r,ll v,int le,int ri,int u){
    if(l<=le && ri<=r){
        add[u]=((add[u]%mod)*(v%mod))%mod;
        mul[u]=((mul[u]%mod)*(v%mod))%mod;
        sum[u]=((sum[u]%mod)*(v%mod))%mod;
        return;
    }
    pushdown(u,ri-le+1);
    int mid=(le+ri)>>1;
    if(l<=mid) cheng(l,r,v,le,mid,u<<1);
    if(r>mid) cheng(l,r,v,mid+1,ri,u<<1|1);
    pushup(u);
}
ll query(int l,int r,int le,int ri,int u){
    if(l<=le && ri<=r) return sum[u];
    pushdown(u,ri-le+1);
    ll ret=0;
    int mid=(le+ri)>>1;
    if(l<=mid) ret=(ret+query(l,r,le,mid,u<<1))%mod;
    if(r>mid) ret=(ret+query(l,r,mid+1,ri,u<<1|1))%mod;
    return ret;
}
int main(){
    cin>>n>>mod;
    for(int i=1;i<=n;i++) cin>>w[i];
    build(1,n,1);
    int m;
    cin>>m;
    memset(add,0,sizeof(add));
    for(int i=0;i<N <<2;i++){
        mul[i]=1;
    }
    while(m--){
        int op,l,r;
        cin>>op>>l>>r;
        ll v;
        if(op==1 || op==2) cin>>v;
        if(op==1){
            cheng(l,r,v,1,n,1);
        }else if(op==2){
            jia(l,r,v,1,n,1);
        }else{
            cout<<query(l,r,1,n,1)<<endl;
        }
    }
    return 0;
}