#include<bits/stdc++.h>
#define int long long
#define ls (u<<1)
#define rs (u<<1|1)
using namespace std;
const int N=1e5+10;
int n,p,m;
int a[N];
struct tr{
    int l,r,sum,lazy,fac;
}tree[N<<2];
void pushup(int u){
    tree[u].sum=tree[ls].sum+tree[rs].sum;
}
void build(int u,int l,int r){
    tree[u]={l,r,0,0,1};
    if(l==r){
        tree[u].sum=a[l];
        return ;
    }
    int mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(u);
}
void pushdown(int u){
    int mul=tree[u].fac,add=tree[u].lazy;
    tree[ls].sum=(tree[ls].sum*mul+(tree[ls].r-tree[ls].l+1)*add)%p;
    tree[rs].sum=(tree[rs].sum*mul+(tree[rs].r-tree[rs].l+1)*add)%p;
    (tree[ls].fac*=mul)%p;
    (tree[rs].fac*=mul)%p;
    tree[ls].sum=(tree[ls].sum*mul+add)%p;
    tree[rs].sum=(tree[rs].sum*mul+add)%p;
    tree[u].fac=1;tree[u].lazy=0;
}
void modify(int u,int l,int r,int k,int op){
    if(l<=tree[u].l&&tree[u].r<=r){
        if(op){
            (tree[u].sum*=k)%=p;
            (tree[u].fac*=k)%=p;
            (tree[u].lazy*=k)%=p;
        }else{
            tree[u].sum=(tree[u].sum+(tree[u].r-tree[u].l+1)*k)%p;
            (tree[u].lazy+=k)%p;
        }
        return ;
    }
    pushdown(u);
    int mid=tree[u].l+tree[u].r>>1;
    if(l<=mid) modify(ls,l,r,k,op);
    if(mid<r) modify(rs,l,r,k,op);
    pushup(u);
}
int query(int u,int l,int r){
    if(l<=tree[u].r&&tree[u].r<=r){
        return tree[u].sum%p;
    }
    pushdown(u);
    int mid=tree[u].l+tree[u].r>>1;
    int ans=0;
    if(l<=mid) ans+=query(ls,l,r)%p;
    if(mid<r) ans+=query(rs,l,r)%p;
    return ans;
}
signed main(){
    scanf("%lld%lld",&n,&p);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    scanf("%lld",&m);
    int op,l,r,k;
    for(int i=1;i<=m;i++){
        scanf("%lld%lld%lld",&op,&l,&r);
        if(op==1){
            scanf("%lld",&k);
            modify(1,l,r,k,1);
        }else if(op==2){
            scanf("%lld",&k);
            modify(1,l,r,k,0);
        }else{
            printf("%lld\n",query(1,l,r));
        }
    }
    return 0;
}