区间乘

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n,m,p;
int w[N];

struct SegTree
{
    int l,r;//[l,r]
    long long sum,add,mul=1;//sum区间查询,add和懒标记,mul积懒标记
}tr[N << 2];
//快读
inline void read(int& x)
{
    x=0;int f = 1;char c = getchar();
    while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}
    while(isdigit(c)){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    x*=f;
}
//向下更新信息
void pushdown(int u)
{
    //根区间，左区间，右区间
    SegTree& root = tr[u],& left = tr[u<<1],& right = tr[u<<1|1];
    //有懒标记就下放
    //左区间的懒标记下放，区间和相当于加上长度*add
    left.mul=left.mul*root.mul%p;
    left.add=(left.add*root.mul+root.add)%p;
    left.sum=((long long)(left.sum*root.mul)+(long long)(left.r-left.l+1)*root.add)%p;
    //右区间同理
    right.mul=right.mul*root.mul%p;
    right.add=(right.add*root.mul+root.add)%p;
    right.sum=((long long)(right.sum*root.mul)+(long long)(right.r-right.l+1)*root.add)%p;
    root.add = 0;
    root.mul = 1;
}
//向上更新回根
void pushup(int u)
{
    //左和+右和
    tr[u].sum = (tr[u<<1].sum+tr[u<<1|1].sum)%p;
}
//递归建树tr[u]存储[l,r]
void build(int u,int l,int r)
{
    if(l == r) tr[u] = {l,r,w[r],0,1};
    else
    {
        tr[u] = {l,r};
        int mid = (l+r)>>1;
        //左子树
        build(u<<1,l,mid);
        //右子树
        build(u<<1|1,mid+1,r);
        //递归建树区间和要上传到根
        pushup(u);
    }
}
//区间修改
void modify(int u,int l,int r,int d)
{
    //在当前区间内部
    if(tr[u].l>=l && tr[u].r<=r)
    {
        //先把区间更新了，区间和相当于加上长度*add
        tr[u].sum=(tr[u].sum+(long long)(tr[u].r-tr[u].l+1)*d)%p;
        //把懒标记更新了
        tr[u].add=(tr[u].add+d)%p;
    }
    else
    {
        //先更新信息，因为要用到子树的性质
        pushdown(u);
        int mid = (tr[u].l+tr[u].r)>>1;
        //当前区间在左半区间
        if(l<=mid) modify(u<<1,l,r,d);
        //当前区间在右半区间
        if(r>mid) modify(u<<1|1,l,r,d);
        //向上更新
        pushup(u);
    }
}

void modify1(int u,int l,int r,int d)
{
    if(tr[u].l>=l && tr[u].r<=r)
    {
        tr[u].sum=tr[u].sum*d%p;
        tr[u].add=tr[u].add*d%p;
        tr[u].mul=tr[u].mul*d%p;
    }
    else
    {
        pushdown(u);
        int mid = (tr[u].l+tr[u].r)>>1;
        if(l<=mid) modify1(u<<1,l,r,d);
        if(r>mid) modify1(u<<1|1,l,r,d);
        pushup(u);
    }
}

//区间查询
long long query(int u,int l,int r)
{
    //就是当前区间
    if(tr[u].l>=l && tr[u].r<=r) return tr[u].sum%p;
    //向下更新
    pushdown(u);
    int mid = (tr[u].l+tr[u].r) >> 1;
    long long sum = 0;
    //当前区间在左半区间
    if(l<=mid) sum += query(u<<1,l,r);
    //当前区间在右半区间
    if(r>mid) sum+=query(u<<1|1,l,r);
    return sum;
}

int main()
{
    read(n),read(p);
    for(int i=1;i<=n;i++) read(w[i]);
    read(m);
    build(1,1,n);
    int op,t,g,c;
    while(m--)
    {
        read(op);
        if(op == 1)
        {
            read(t),read(g),read(c);
            modify1(1,t,g,c);
        }
        else if(op == 2)
        {
            read(t),read(g),read(c);
            modify(1,t,g,c);
        }
        else
        {
            read(t),read(g);
            printf("%lld\n",query(1,t,g)%p);
        }
    }
    return 0;
}