data

input

8 100 10000000
3 1 6 9 4 7 5 3
3 4 7
2 1 6 4
1 3 3 4
1 3 6 6
3 2 8
3 4 5
2 1 7 10
1 1 2 6
3 2 7
3 4 7
2 7 7 1
2 3 5 10
2 4 7 7
3 8 8
1 2 7 6
1 2 6 4
3 6 8
1 1 8 1
1 2 2 8
3 4 6
2 4 7 9
1 3 7 1
1 2 4 5
2 6 8 10
1 7 7 7
3 7 8
1 7 8 4
3 2 7
1 6 6 8
1 7 7 8
3 2 4
3 3 3
2 1 5 10
1 3 7 7
3 1 5
2 4 5 8
3 2 8
1 6 6 10
1 1 3 9
2 4 6 3
1 4 5 5
2 5 7 3
1 3 4 8
1 2 8 9
3 7 8
3 3 7
1 4 5 4
2 2 3 3
3 1 2
1 3 7 7
2 1 4 8
1 5 6 2
1 7 7 4
2 3 6 1
1 3 7 1
1 6 6 10
1 6 6 6
3 3 3
3 5 5
1 1 8 4
1 4 6 10
3 4 5
1 3 4 4
1 3 8 7
2 2 8 5
3 6 7
2 5 8 7
3 6 6
3 4 5
2 3 7 3
2 1 6 6
2 4 7 10
2 5 8 7
2 3 6 8
2 3 6 8
3 3 8
1 4 8 7
1 6 8 4
1 7 8 2
3 2 4
2 1 2 7
2 6 8 5
3 4 6
1 1 6 4
1 8 8 4
3 6 8
2 3 4 5
2 3 8 4
1 1 1 1
1 2 7 8
1 2 4 2
1 2 7 4
1 4 7 10
2 7 8 7
1 1 5 5
3 1 1
1 5 7 1
1 5 7 10
2 5 6 4
2 2 7 7

output

25
445
126
577
237
3
2133
6312
1112
138461
130245
31200
406310
765058
2216079
6387732
7000221
979950
2116393
6563280
5244634
8205612
6001737
1014077
1633365
1771015
6159981
81540

wrong:

25
421
126
533
203
3
2133
6144
1112
138461
130245
31200
406230
765058
2216079
6387705
7000221
979950
2116393
6563280
5244634
8205612
6001737
1014000
1633365
1771015
6159981
81540

std

#include
#include
#define Rll register long long
#define ll long long
#define Rint register int
long long ans[400010],lazy1[400010],lazy2[400010];
int n,m,o,p,L,R,C,sp;
using namespace std;
inline void pushup(int rt)
{
    ans[rt]=(ans[rt<<1]+ans[rt<<1|1])%p;
}
inline void build(Rll l,Rll r,Rint rt)
{
    sp=max(sp,rt);
    lazy1[rt]=1;
    lazy2[rt]=0;
    if (l==r)
    {
        scanf("%lld",&ans[rt]);
        ans[rt]=ans[rt]%p;
        return;
    }
    Rll mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
inline void pushdown(Rint rt,Rint ln,Rint rn)
{
    if (lazy1[rt]!=1)
    {
        lazy1[rt<<1]=lazy1[rt<<1]*lazy1[rt]%p;
        lazy1[rt<<1|1]=lazy1[rt<<1|1]*lazy1[rt]%p;
        lazy2[rt<<1]=lazy2[rt<<1]*lazy1[rt]%p;
        lazy2[rt<<1|1]=lazy2[rt<<1|1]*lazy1[rt]%p;
        ans[rt<<1]=lazy1[rt]*ans[rt<<1]%p;
        ans[rt<<1|1]=ans[rt<<1|1]*lazy1[rt]%p;
        lazy1[rt]=1;
    }
    if (lazy2[rt])
    {
        lazy2[rt<<1]=(lazy2[rt<<1]+lazy2[rt])%p;
        lazy2[rt<<1|1]=(lazy2[rt<<1|1]+lazy2[rt])%p;
        ans[rt<<1]=(ans[rt<<1]+lazy2[rt]*ln%p)%p;
        ans[rt<<1|1]=(ans[rt<<1|1]+lazy2[rt]*rn%p)%p;
        lazy2[rt]=0;
    }
}
inline void update1(Rll L,Rll R,Rll C,Rll l,Rll r,Rll rt)
{
    if (L<=l&&r<=R)
    {
        ans[rt]=ans[rt]*C%p;
        lazy1[rt]=lazy1[rt]*C%p;
        lazy2[rt]=lazy2[rt]*C%p;
        return;
    }
    Rll mid=(l+r)>>1;
    pushdown(rt,mid-l+1,r-mid);
    if (L<=mid) update1(L,R,C,l,mid,rt<<1);
    if (R>mid) update1(L,R,C,mid+1,r,rt<<1|1);
    pushup(rt);
}
inline void update2(Rll L,Rll R,Rll C,Rll l,Rll r,Rll rt)
{
    if (L<=l&&r<=R)
    {
        ans[rt]=(ans[rt]+C*(r-l+1)%p)%p;
        lazy2[rt]=(lazy2[rt]+C)%p;
        return;
    }
    Rll mid=(l+r)>>1;
    pushdown(rt,mid-l+1,r-mid);
    if (L<=mid) update2(L,R,C,l,mid,rt<<1);
    if (R>mid) update2(L,R,C,mid+1,r,rt<<1|1);
    pushup(rt);
}
inline ll query(Rll L,Rll R,Rll l,Rll r,Rll rt)
{
    if (L<=l&&r<=R)
        return ans[rt];
    Rll mid=(l+r)>>1;
    pushdown(rt,mid-l+1,r-mid);
    Rll ans=0;
    if (L<=mid) ans=(ans+query(L,R,l,mid,rt<<1))%p;
    if (R>mid) ans=(ans+query(L,R,mid+1,r,rt<<1|1))%p;
    return ans;
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("testing.out","w",stdout);
    scanf("%d%d%d",&n,&m,&p);
    build(1,n,1);
    for(int i=1;i<=m;++i)
    {
        scanf("%d",&o);
        if(o==1)
        {
            scanf("%d%d%d",&L,&R,&C);
            update1(L,R,C,1,n,1);  
        }else
        if(o==2)
        {
            scanf("%d%d%d",&L,&R,&C);
               update2(L,R,C,1,n,1);  
        }
        else
        {    
            scanf("%d%d",&L,&R);
            printf("%lld\n",query(L,R,1,n,1));
        }
    }
    return 0;
}