#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define PII pair<int,int>
using namespace std;
const int N =  1 *1e6 + 10,M = 5 * 1e3 + 10,inf = 0x3f3f3f3f;

int n,m,p,a[N];
struct node{
    int l,r;
    int sum,add,mul;
}tr[N*4];
void eval(node &root,int add,int mul){
    root.sum = ((LL)root.sum * mul + (LL)(root.r - root.l + 1) * add) % p;
    root.mul = (LL)root.mul * mul % p;
    root.add = ((LL)root.add * mul + add) % p;
}
void pushup(int u){
    tr[u].sum = (tr[u<<1].sum + tr[u<<1|1].sum) % p;
}
void pushdown(int u){
    eval(tr[u<<1],tr[u].add,tr[u].mul);
    eval(tr[u<<1|1],tr[u].add,tr[u].mul);
    tr[u].add = 0 , tr[u].mul = 1;
}
void build(int u,int l,int r){
    if(l==r) tr[u] = {l,r,a[r],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,int add,int mul){
    if(tr[u].l >= l && tr[u].r <= r) eval(tr[u],add,mul);
    else{
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) modify(u<<1,l,r,add,mul);
        if(r > mid) modify(u<<1|1,l,r,add,mul);
        pushup(u);
    }
}
int query(int u,int l,int r){
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    if(l <= mid) sum = query(u<<1,l,r);
    if(r > mid) sum = (sum + query(u<<1|1,l,r)) % p; 
    return sum;
}
void solve(){
    cin >> n >> p;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1,1,n);
    cin >> m;
    while (m--){
        int op,l,r,x;
        cin >> op >> l >> r;
        if(op == 3){
            cout<<query(1,l,r)<<endl;
        }
        else{
            cin>>x;
            if(op == 1) modify(1,l,r,0,x);
            if(op == 2) modify(1,l,r,x,1);
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(nullptr),cout.tie(0);
    int _=1;
    // cin>>_;
    while(_--){
        solve();
    }
    return 0;
}

/**
 *    author: Nijika_jia
 *    created: 2024.10.15 00:15:07
 */
```


```