维护序列
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rd(x) scanf("%d",&x)
const int N=1e5+10;
int w[N];
int n,m,p;

struct node
{
    int l,r;
    int sum;
    int add,mul;
}tr[N*4];
void eval(node &u,int add,int mul)//计算s*mul+add
{
    u.sum=((ll)u.sum*mul+(ll)add*(u.r-u.l+1))%p;//这里加的时候记得是(ll)add*(u.r-u.l+1)
    u.mul=(ll)u.mul*mul%p;
    u.add=((ll)u.add*mul+add)%p;
}
void pushup(int u)
{
    tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%p;
}
void pushdown(int u)
{
    int &a=tr[u].add,&b=tr[u].mul;
    eval(tr[u<<1],a,b);
    eval(tr[u<<1|1],a,b);
    a=0,b=1;
}
void build(int u,int l,int r)
{
    if(l==r)    tr[u]={r,r,w[r],0,1};
    else
    {
        tr[u]={l,r,0,0,1};//这里老是忘记写
        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 add,int mul)
{
    if(tr[u].l>=l&&tr[u].r<=r)  eval(tr[u],add,mul);
    else
    {
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid)  modify(u<<1,l,r,add,mul);
        if(r>mid)   modify(u<<1|1,l,r,add,mul);
        pushup(u);
    }
}

ll query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r)  return tr[u].sum;
    else
    {
        pushdown(u);
        ll res=0;
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid)  res+=query(u<<1,l,r);
        if(r>mid)   res=(res+query(u<<1|1,l,r))%p;
        return res;
    }
}

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