https://www.luogu.com.cn/record/128898410

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q,mod;
int a[100010];
int lf[400010],rt[400010];
int times[400010],pls[400010],res[400010];
void build(int x,int l,int r)
{
    lf[x]=l;
    rt[x]=r;
    times[x]=1;
    if(l==r)
    {
        res[x]=a[l]%mod;
        return;
    }
    int mid=(l+r)/2;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    res[x]=(res[x<<1]+res[x<<1|1])%mod;
}
void pd(int x)
{
    if(lf[x]==rt[x])
    {
        return;
    }
    if(times[x]==1&&pls[x]==0)
    {
        return;
    }
    pls[x<<1]=(pls[x<<1]*times[x]%mod+pls[x])%mod;
    pls[x<<1|1]=(pls[x<<1|1]*times[x]%mod+pls[x])%mod;
    times[x<<1]=times[x<<1]*times[x]%mod;
    times[x<<1|1]=times[x<<1|1]*times[x]%mod;
    res[x<<1]=(res[x<<1]*times[x]%mod+pls[x]*(rt[x<<1]-lf[x<<1]+1))%mod;
    res[x<<1|1]=(res[x<<1|1]*times[x]%mod+pls[x]*(rt[x<<1|1]-lf[x<<1|1]+1))%mod;
    pls[x]=0;
    times[x]=1;
}
int calc(int x,int l,int r)
{
    if(l<=lf[x]&&rt[x]<=r)
    {
        return res[x];
    }
    if(r<lf[x]||rt[x]<l)
    {
        return 0;
    }
    pd(x);
    int ans1=calc(x<<1,l,r),ans2=calc(x<<1|1,l,r);
    return (ans1+ans2)%mod;
}
void updt(int x,int l,int r,int k)
{
    if(l<=lf[x]&&rt[x]<=r)
    {
        res[x]=res[x]*k%mod;
        times[x]=times[x]*k%mod;
        return ;
    }
    if(r<lf[x]||rt[x]<l)
    {
        return ;
    }
    pd(x);
    updt(x<<1,l,r,k);
    updt(x<<1|1,l,r,k);
    res[x]=(res[x<<1]+res[x<<1|1])%mod;
}
void updp(int x,int l,int r,int k)
{
    if(l<=lf[x]&&rt[x]<=r)
    {
        res[x]=(res[x]+k*(rt[x]-lf[x]+1))%mod;
        pls[x]=(pls[x]+k)%mod;
        return ;
    }
    if(r<lf[x]||rt[x]<l)
    {
        return ;
    }
    pd(x);
    updp(x<<1,l,r,k);
    updp(x<<1|1,l,r,k);
    res[x]=(res[x<<1]+res[x<<1|1])%mod;
}
signed main()
{
    cin >> n >> q >> mod;
    for ( int i = 1 ; i <= n ; i++ )
    {
        cin >> a[i];
    }
    build(1,1,n);
    while(q--)
    {
        int op,l,r,k;
        cin >> op >> l >> r;
        if(r<l)
        {
            swap(l,r);
        }
        if(op==3)
        {
            cout << calc(1,l,r) << endl;
        }else
        {
            cin >> k;
            if(op==1)
            {
                updt(1,l,r,k);
            }else{
                updp(1,l,r,k);
            }
        }
    }
    return 0;
}