#include <bits/stdc++.h>
#define LL long long
#define ll long long
const int N = 1e6 + 10;
using namespace std;
ll MOD;
int n, m;
ll w[N];
struct node {
    int l,r;
    ll sum,add;
    ll malt;
} tr[N*4];
void cal(node &t, ll c, ll j) {
    // u.add+=d;
    t.sum = (t.sum*c + (t.r-t.l+1)*j) % MOD;
    t.add = (t.add * c + j) % MOD;
    t.malt = t.malt * c % MOD;
    //tr[u << 1].sum = ((ll)tr[u << 1].sum * tr[u].malt + (ll)tr[u].add * (tr[u << 1].r - tr[u << 1].l + 1)) % p;
    //tr[u << 1].add = ((ll)tr[u << 1].add * tr[u].malt + tr[u].add) % p;
    //tr[u << 1].malt = (ll)tr[u << 1].malt * tr[u].malt % p;

}
void pushup2(node &u, node &l, node &r) {
    u.sum = (l.sum + r.sum) % MOD;
}
void pushup(int u) {
    pushup2(tr[u], tr[u << 1], tr[u << 1|1]);
}
void pushdown(int u){
    node &root = tr[u], &left = tr[u<<1], &right = tr[u<<1|1];
    cal(left, root.malt, root.add);
    cal(right, root.malt, root.add);
    root.add = 0;
    root.malt = 1;
}
ll query(int u,int l,int r){
    if(l<=tr[u].l && tr[u].r<=r){
        return tr[u].sum;
    }else{
        pushdown(u);
        ll res=0;
        int mid=(tr[u].l+tr[u].r)/2;
        if(mid>=l){
            res+=query(u<<1,l,r) % MOD;
        }if(mid<r){
            res+=query(u<<1|1,l,r) % MOD;
        }
        return res % MOD;
    }

}

void build(int u,int l,int r){
    if(l==r) tr[u]={r,l,w[l],0,1};
    else{
        tr[u] = {l,r,0,0,1};
        int mid=(l+r)>>1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
void modify(int u,int l,int r,ll d,ll c){
    if(l<=tr[u].l && tr[u].r<=r){
        cal(tr[u],c,d);
    }else{
        pushdown(u);
        int mid=(tr[u].l+tr[u].r)/2;
        if(mid>=l){
            modify(u<<1,l,r,d,c);
        }if(r>mid){
            modify(u<<1|1,l,r,d,c);
        }
        pushup(u);
    }
}

int main () { 
    cin>>n>>MOD;
    int op,l,r,d;
    for(int i=1;i<=n;i++) cin>>w[i];
    cin>>m;
    build (1,1,n);
    for(int i=1;i<=m;i++){
        cin>>op>>l>>r;
        if(op==1){
            cin>>d;
            modify(1,l,r,0,d);
        }else if(op==2){
            cin>>d;
            modify(1,l,r,d,1);
        }else{
            cout<<query(1,l,r)%MOD<<endl;
        }
    }
}