#include<bits/stdc++.h>
using namespace std;
#define mod 571373
#define ls(k) (k)<<1
#define rs(k) ((k)<<1)+1
#define int long long
int n,m,a[500009],x,y,z,op,sum[2000009],add[2000009],mul[2000009],mo;
void build(int k,int l,int r){
	  mul[k]=1;
    if(l==r){
        sum[k]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls(k),l,mid);
    build(rs(k),mid+1,r);
    sum[k]=(sum[ls(k)]+sum[rs(k)])%mod;
}
inline void ad(int k,int l,int r,int v){
    add[k]+=v;
    add[k]%=mod;
    sum[k]+=v*(r-l+1);
    sum[k]%=mod;
}
inline void ml(int k,int l,int r,int v){
    add[k]*=v;
    add[k]%=mod;
    mul[k]*=v;
    mul[k]%mod;
    sum[k]*=v;
    sum[k]%=mod;
}
void pushdown(int k,int l,int r,int mid){
    ml(ls(k),l,mid,mul[k]);
    ad(ls(k),l,mid,add[k]);
    ml(rs(k),mid+1,r,mul[k]);
    ad(rs(k),mid+1,r,add[k]);
    add[k]=0;
    mul[k]=1;
} 
void ADD(int k,int l,int r,int x,int y,int v){
    if(l>=x&&r<=y){
        ad(k,l,r,v);
        return;
    }
    int mid=(l+r)>>1;
    pushdown(k,l,r,mid);
    if(x<=mid){
        ADD(ls(k),l,mid,x,y,v);
    }
    if(mid<y){
        ADD(rs(k),mid+1,r,x,y,v);
    }
    sum[k]=(sum[ls(k)]+sum[rs(k)])%mod;
}
void MUL(int k,int l,int r,int x,int y,int v){
    if(l>=x&&r<=y){
        ml(k,l,r,v);
        return;
    }
    int mid=(l+r)>>1;
    pushdown(k,l,r,mid);
    if(x<=mid){
        MUL(ls(k),l,mid,x,y,v);
    }
    if(mid<y){
        MUL(rs(k),mid+1,r,x,y,v);
    }
    sum[k]=(sum[ls(k)]+sum[rs(k)])%mod;
}
int query(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y){
        return sum[k];
    }
    int mid=(l+r)>>1,ans=0;
    pushdown(k,l,r,mid);
    if(x<=mid){
        ans=query(ls(k),l,mid,x,y);
        ans%=mod;
    }
    if(mid<y){
        ans+=query(rs(k),mid+1,r,x,y);
        ans%=mod;
    }
    return ans%mod;
}
signed main(){
    cin>>n>>m>>mo;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    while(m--){
        cin>>op>>x>>y;
        if(op==2){            
            cin>>z;
            ADD(1,1,n,x,y,z);
        }
        else if(op==1){
            cin>>z;
            MUL(1,1,n,x,y,z);                                 
        }
        else{
            cout<<query(1,1,n,x,y)<<'\n';
        }
    }
    return 0;
}