[Ahoi 2009] 유지 보수 시퀀스

#include
#define ll long long
#define il inline
#define ls p<<1
#define rs p<<1|1
#define M 100005
using namespace std;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
il int read(){
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=(x+(x<<2)<<1)+c-48;
    return x*f;
}
char sr[1<<21],z[20];int C=-1,Z;
il void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
il void print(ll x){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='
';
}
ll n,m,mo,c,d,e;
ll a[M],sum[M<<2],j[M<<2],b[M<<2];
il void push_up(ll p){sum[p]=(sum[ls]+sum[rs])%mo;}
il void build(ll p,ll l,ll r){
    b[p]=1;j[p]=0;
    if(l==r){sum[p]=a[l]%mo; return;}
    ll mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    push_up(p);
}
il void push_down(ll p,ll l,ll r){
    ll mid=l+r>>1;
    sum[ls]=(sum[ls]*b[p])%mo;
    sum[ls]=(sum[ls]+j[p]*(mid-l+1))%mo;
    sum[rs]=(sum[rs]*b[p])%mo;
    sum[rs]=(sum[rs]+j[p]*(r-mid))%mo;
    j[ls]=(j[ls]*b[p]+j[p])%mo;
    j[rs]=(j[rs]*b[p]+j[p])%mo;
    b[ls]=(b[ls]*b[p])%mo;
    b[rs]=(b[rs]*b[p])%mo;
    b[p]=1;j[p]=0;
}
il void mul(ll p,ll l,ll r,ll L,ll R,ll x){
    if(L>r||l>R) return;
    if(L<=l&&r<=R){
        sum[p]=(sum[p]*x)%mo;
        b[p]=(b[p]*x)%mo;
        j[p]=(j[p]*x)%mo;
        return; 
    }
    push_down(p,l,r);
    ll mid=l+r>>1;
    mul(ls,l,mid,L,R,x);
    mul(rs,mid+1,r,L,R,x);
    push_up(p);
}
il void add(ll p,ll l,ll r,ll L,ll R,ll x){
    if(L>r || l>R) return;
    if(L<=l && r<=R){
        j[p]=(j[p]+x)%mo;
        sum[p]=(sum[p]+x*(r-l+1))%mo; 
        return;
    }
    push_down(p,l,r);
    ll mid=l+r>>1;
    add(ls,l,mid,L,R,x);add(rs,mid+1,r,L,R,x);
    push_up(p);
}
il ll query(ll p,ll l,ll r,ll L,ll R){
    if(L>r || l>R) return 0;
    if(L<=l && r<=R) return sum[p]%mo;
    push_down(p,l,r);
    ll mid=l+r>>1;
    return(query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R))%mo;
}
int main(){
    n=read();mo=read();
    for(int i=1;i<=n;++i)
    a[i]=read()%mo;
    build(1,1,n);
    m=read();
    for(int i=1;i<=m;++i){
        c=read(),d=read(),e=read();
        if(c==1) mul(1,1,n,d,e,read()%mo);
        else if(c==2) add(1,1,n,d,e,read()%mo);
        else print(query(1,1,n,d,e));
    }Ot();return 0;
}