#include<bits/stdc++.h>
using namespace std;
const int maxn=100001;
long long p;
long long a[maxn];
int n,m;
struct node{
   int l,r;
   long long s,add,mul;
}tr[3*maxn];
void pushdown(int k){ 
    if(tr[k].mul!=1){
        tr[2*k].add*=tr[k].mul; tr[2*k].add%=p;
        tr[2*k+1].add*=tr[k].mul; tr[2*k+1].add%=p;
        tr[2*k].mul*=tr[k].mul; tr[2*k].mul%=p;
        tr[2*k+1].mul*=tr[k].mul; tr[2*k+1].mul%=p;
        tr[2*k].s*=tr[k].mul; tr[2*k].s%=p;
        tr[2*k+1].s*=tr[k].mul; tr[2*k+1].s%=p;
        tr[k].mul=1;
    }
    if(tr[k].add){
        tr[2*k].add+=tr[k].add; tr[2*k].add%=p;
        tr[2*k+1].add+=tr[k].add; tr[2*k+1].add%=p;
        tr[2*k].s+=tr[k].add*(tr[2*k].r-tr[2*k].l+1);
        tr[2*k].s%=p;
        tr[2*k+1].s+=tr[k].add*(tr[2*k+1].r-tr[2*k+1].l+1);
        tr[2*k+1].s%=p;
        tr[k].add=0;
    }
}

void pushup(int k){
    tr[k].s=(tr[2*k].s+tr[2*k+1].s)%p;
}
void build(int k,int l,int r){
    tr[k].l=l,tr[k].r=r,tr[k].add=0;
    if(l==r) {tr[k].s=a[l]%p;return ;}
    int mid=(l+r)>>1;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    pushup(k);
}
void update(int k,int x,int y,long long c,bool t){
    if(x>tr[k].r||y<tr[k].l) return;
    if(x<=tr[k].l&&y>=tr[k].r) {
        if(t==0){
            tr[k].add+=c; tr[k].add%=p;
            tr[k].s+=c*(tr[k].r-tr[k].l+1);
            tr[k].s%=p;
        }else{
            tr[k].mul*=c; tr[k].mul%=p;
            tr[k].add*=c; tr[k].add%=p;
            tr[k].s*=c; tr[k].s%=p;
        }
        return;

    }
    pushdown(k);
    update(2*k,x,y,c,t);
    update(2*k+1,x,y,c,t);
    pushup(k);
}
long long query(int k,int x,int y){
    if(x>tr[k].r||y<tr[k].l) return 0;
    if(x<=tr[k].l&&y>=tr[k].r) return tr[k].s;
    pushdown(k);
//  pushup(k);
    return (query(2*k,x,y)+query(2*k+1,x,y))%p;
}
int main(){
    cin>>n>>p;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=300000;i++) tr[i].mul=1;
    build(1,1,n);
    cin>>m;
    for(int i=1;i<=m;i++){
        int t,x,y;
        long long c;
        scanf("%d",&t);
        if(t==1) {
            scanf("%d%d%lld",&x,&y,&c);
            update(1,x,y,c,1);
        }
        else if(t==2){
            scanf("%d%d%lld",&x,&y,&c);
            update(1,x,y,c,0);
        }
        else{
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(1,x,y)%p);
        }
    }
}