#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define mid ((l+r)>>1)

using namespace std;

typedef long long ll;

int const xn=1e5+;

int n,a[xn],cnt,ls[xn<<],rs[xn<<],sum[xn<<],lzy[xn<<],ml[xn<<],p;

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return f?ret:-ret;

}

int upt(int x){while(x>=p)x-=p; while(x<)x+=p; return x;}

void build(int x,int l,int r)

{

  ml[x]=;//

  if(l==r){sum[x]=a[l]; return;}

  ls[x]=++cnt; rs[x]=++cnt;

  build(ls[x],l,mid); build(rs[x],mid+,r);

  sum[x]=upt(sum[ls[x]]+sum[rs[x]]);

}

void turn(int x,int c){sum[x]=(ll)sum[x]*c%p; lzy[x]=(ll)lzy[x]*c%p; ml[x]=(ll)ml[x]*c%p;}

void pushdown(int x,int l,int r)

{

  if(ml[x]!=)//

    {

      int v=ml[x]; ml[x]=;//

      turn(ls[x],v); turn(rs[x],v);

    }

  if(lzy[x])

    {

      int v=lzy[x]; lzy[x]=;

      sum[ls[x]]=(sum[ls[x]]+(ll)(mid-l+)*v)%p; lzy[ls[x]]=upt(lzy[ls[x]]+v);

      sum[rs[x]]=(sum[rs[x]]+(ll)(r-mid)*v)%p; lzy[rs[x]]=upt(lzy[rs[x]]+v);

    }

}

void mul(int x,int l,int r,int L,int R,int c)

{

  if(l>=L&&r<=R){turn(x,c); return;}

  pushdown(x,l,r);

  if(mid>=L)mul(ls[x],l,mid,L,R,c);

  if(mid<R)mul(rs[x],mid+,r,L,R,c);

  sum[x]=upt(sum[ls[x]]+sum[rs[x]]);

}

void add(int x,int l,int r,int L,int R,int c)

{

  if(l>=L&&r<=R){sum[x]=(sum[x]+(ll)(r-l+)*c)%p; lzy[x]=upt(lzy[x]+c); return;}

  pushdown(x,l,r);

  if(mid>=L)add(ls[x],l,mid,L,R,c);

  if(mid<R)add(rs[x],mid+,r,L,R,c);

  sum[x]=upt(sum[ls[x]]+sum[rs[x]]);

}

int query(int x,int l,int r,int L,int R)

{

  if(l>=L&&r<=R)return sum[x];

  pushdown(x,l,r); int ret=;

  if(mid>=L)ret=upt(ret+query(ls[x],l,mid,L,R));

  if(mid<R)ret=upt(ret+query(rs[x],mid+,r,L,R));

  return ret;

}

int main()

{

  n=rd(); p=rd();

  for(int i=;i<=n;i++)a[i]=rd()%p;

  build(++cnt,,n);

  int m=rd();

  for(int i=,tp,l,r,c;i<=m;i++)

    {

      tp=rd(); l=rd(); r=rd();

      if(tp==)c=rd()%p,mul(,,n,l,r,c);

      if(tp==)c=rd()%p,add(,,n,l,r,c);

      if(tp==)printf("%d\n",query(,,n,l,r));

    }

  return ;

}