分块求优化啊，写了80分

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define int long long
#define maxn 100005
#define maxm 1005
using namespace std;
int n,m,p,blo,a[maxn],d[maxn],len;
int add[maxm],x[maxm],sum[maxn];
void re(int u)
{
    int s=min(n,(u)*blo);
    sum[u]=0;
    for(int i=(u-1)*blo+1;i<=s;i++){
        a[i]=a[i]*x[u]+add[u];
        a[i]%=p;
        sum[u]+=a[i];
    }
    sum[u]%=p;
    add[u]=0;x[u]=1;
}
long long query(int fr,int to)
{
    // cout<<fr<<" "<<to<<endl;
    int ans=0;
    int s=min(to,(d[fr])*blo);
// 	cout<<s<<" s"<<endl;
    re(d[fr]);
    for(int i=fr;i<=s;i++){
       // cout<<i<<" i"<<endl;
        ans+=a[i];
// 		cout<<ans<<" ans"<<endl;
        ans%=p;
    }
    if(d[fr]!=d[to]){
        re(d[to]);
        for(int i=(d[to]-1)*blo+1;i<=to;i++){
          //  cout<<i<<" i"<<endl;
            ans+=a[i];
// 			cout<<ans<<" ans"<<endl;
            ans%=p;
        }
    }
    for(int i=d[fr]+1;i<d[to];i++){
       // cout<<i<<" ???0"<<endl;
        ans+=sum[i]*x[i];
        ans%=p;
        ans+=add[i]*blo;
        ans%=p;
    }
    return ans;
}


void xx(int fr,int to,int c)
{
    int s=min(to,(d[fr])*blo);
    re(d[fr]);
    for(int i=fr;i<=s;i++){
        sum[d[i]]-=a[i];
        if(sum[d[i]]<0) sum[d[i]]+=p;
        a[i]*=c;
        a[i]%=p;
        sum[d[i]]+=a[i];
    }
    sum[d[fr]]%=p;
    if(d[fr]!=d[to]){
        re(d[to]);
        for(int i=(d[to]-1)*blo+1;i<=to;i++){
            sum[d[i]]-=a[i];
            if(sum[d[i]]<0) sum[d[i]]+=p;
            a[i]*=c;
            a[i]%=p;
            sum[d[i]]+=a[i];
        }
    sum[d[to]]%=p;
    }
    for(int i=d[fr]+1;i<d[to];i++){
        x[i]*=c;x[i]%=p;
        add[i]*=c;add[i]%=p;
    }
}
void jiajia(int fr,int to,int c)
{
    int s=min(to,(d[fr]*blo));
    re(d[fr]);
    for(int i=fr;i<=s;i++){
        sum[d[i]]-=a[i];
        if(sum[d[i]]<0) sum[d[i]]+=p;
        a[i]+=c;
        a[i]%=p;
        sum[d[i]]+=a[i];
    }
    sum[d[fr]]%=p;
    if(d[fr]!=d[to]){
        re(d[to]);
        for(int i=(d[to]-1)*blo+1;i<=to;i++){
            sum[d[i]]-=a[i];
            if(sum[d[i]]<0) sum[d[i]]+=p;
            a[i]+=c;
            a[i]%=p;
            sum[d[i]]+=a[i];
        }
        
    sum[d[to]]%=p;
    }
    for(int i=d[fr]+1;i<d[to];i++){
        add[i]+=c;add[i]%=p;
    }
}

void sc()
{
    scanf("%lld%lld",&n,&p);blo=sqrt(n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),d[i]=(i-1)/blo+1;
    for(int i=1;i<=n;i++) sum[d[i]]+=a[i],x[d[i]]=1,sum[d[i]]%=p;
}
#undef int
int main()
{
    sc();
    scanf("%lld",&m);
    while(m--){
        long long opt,fr,to,c;scanf("%lld",&opt);
        if(opt==1){
            scanf("%lld%lld%lld",&fr,&to,&c);
            xx(fr,to,c);
        }
        if(opt==2){
            scanf("%lld%lld%lld",&fr,&to,&c);
            jiajia(fr,to,c);
        }
        if(opt==3){
            scanf("%lld%lld",&fr,&to);
            printf("%lld\n",query(fr,to));
        }
    }
    return 0;
}