#include <cstdio>

 const long long Maxn=;

 long long a[Maxn],n,P,l,r,c,m,type;

 struct Node

 {

     long long mul,add,sum,len;

 }tree[Maxn<<];

 inline void Change(long long o,long long mul,long long add)

 {

     tree[o].mul=(tree[o].mul*mul)%P;

     tree[o].add=(tree[o].add*mul+add)%P;

     tree[o].sum=(tree[o].sum*mul+tree[o].len*add)%P;

 }

 inline void push_down(long long o)

 {

     Change(o<<,tree[o].mul,tree[o].add);

     Change(o<<|,tree[o].mul,tree[o].add);

     tree[o].mul=; tree[o].add=;

 }

 inline void push_up(long long o)

 {

     tree[o].sum=(tree[o<<].sum+tree[o<<|].sum)%P;

     tree[o].len=tree[o<<].len+tree[o<<|].len;

 }

 void Build(long long o,long long l,long long r)

 {

     tree[o].mul=; tree[o].add=;

     if (l==r) {tree[o].sum=a[l]; tree[o].len=; return;}

     long long mid=(l+r)>>;

     Build(o<<,l,mid),Build(o<<|,mid+,r);

     push_up(o);

 }

 void Mul(long long o,long long l,long long r,long long p,long long q,long long v)

 {

     if (l==p && r==q)

     {

         Change(o,v,);

         return;

     }

     push_down(o);

     long long mid=(l+r)>>;

     if (q<=mid) Mul(o<<,l,mid,p,q,v);

     if (p>=mid+) Mul(o<<|,mid+,r,p,q,v);

     if (p<=mid && q>=mid+)

         Mul(o<<,l,mid,p,mid,v),Mul(o<<|,mid+,r,mid+,q,v);

     push_up(o);

 }

 void Add(long long o,long long l,long long r,long long p,long long q,long long v)

 {

     if (l==p && r==q)

     {

         Change(o,,v);

         return;

     }

     push_down(o);

     long long mid=(l+r)>>;

     if (q<=mid) Add(o<<,l,mid,p,q,v);

     if (p>=mid+) Add(o<<|,mid+,r,p,q,v);

     if (p<=mid && q>=mid+)

         Add(o<<,l,mid,p,mid,v),Add(o<<|,mid+,r,mid+,q,v);

     push_up(o);

 }

 long long Sum(long long o,long long l,long long r,long long p,long long q)

 {

     if (l==p && r==q) return tree[o].sum;

     long long mid=(l+r)>>;

     push_down(o);

     if (q<=mid) return Sum(o<<,l,mid,p,q);

     if (p>=mid+) return Sum(o<<|,mid+,r,p,q);

     if (p<=mid && q>=mid+)

         return (Sum(o<<,l,mid,p,mid)+Sum(o<<|,mid+,r,mid+,q))%P;

 }

 int main()

 {

     // freopen("c.in","r",stdin);

     scanf("%lld%lld",&n,&P);

     for (long long i=;i<=n;i++) scanf("%lld",&a[i]);

     Build(,,n);

     scanf("%lld",&m);

     for (long long i=;i<=m;i++)

     {

         scanf("%lld",&type);

         if (type==)

         {

             scanf("%lld%lld%lld",&l,&r,&c);

             Mul(,,n,l,r,c);

         }

         if (type==)

         {

             scanf("%lld%lld%lld",&l,&r,&c);

             Add(,,n,l,r,c);

         }

         if (type==)

         {

             scanf("%lld%lld",&l,&r);

             printf("%lld\n",Sum(,,n,l,r));

         }

     }

     return ;

 }

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <iostream>

 #define LL long long

 using namespace std;

 const LL Maxn=;

 const LL Inf=0x3f3f3f3f;

 LL a[Maxn],n,P,l,r,c,m,type,Block[Maxn];

 struct Node

 {

     LL mul,add,len,sum;

 }tree[Maxn];

 inline void Change(LL o,LL mul,LL add)

 {

     tree[o].mul=(tree[o].mul*mul)%P;

     tree[o].add=(tree[o].add*mul+add)%P;

     tree[o].sum=(tree[o].sum*mul+tree[o].len*add)%P;

 }

 inline void push_down(LL o)

 {

     for (;Block[o]==Block[o-];o--);

     for (LL i=o;Block[o]==Block[i];i++) a[i]=(a[i]*tree[Block[i]].mul+tree[Block[i]].add)%P;

     tree[Block[o]].mul=,tree[Block[o]].add=;

 }

 inline void push_up(LL o)

 {

     tree[Block[o]].sum=;

     for (;Block[o]==Block[o-];o--);

     for (LL i=o;Block[o]==Block[i];i++) tree[Block[o]].sum=(tree[Block[o]].sum+a[i])%P;

 }

 void Mul(LL p,LL q,LL v)

 {

     if (Block[p]==Block[q])

     {

         push_down(p);

         for (LL i=p;i<=q;i++) a[i]=(a[i]*v)%P;

         push_up(p);

         return;

     }

     for (LL i=Block[p]+;i<Block[q];i++) Change(i,v,);

     push_down(p),push_down(q);

     for (LL i=p;Block[i]==Block[p];i++) a[i]=(a[i]*v)%P;

     for (LL i=q;Block[i]==Block[q];i--) a[i]=(a[i]*v)%P;

     push_up(p),push_up(q);

 }

 void Add(LL p,LL q,LL v)

 {

     if (Block[p]==Block[q])

     {

         push_down(p);

         for (LL i=p;i<=q;i++) a[i]=(a[i]+v)%P;

         push_up(p);

         return;

     }

     for (LL i=Block[p]+;i<Block[q];i++) Change(i,,v);

     push_down(p),push_down(q);

     for (LL i=p;Block[i]==Block[p];i++) a[i]=(a[i]+v)%P;

     for (LL i=q;Block[i]==Block[q];i--) a[i]=(a[i]+v)%P;

     push_up(p),push_up(q);

 }

 LL Sum(LL p,LL q)

 {

     LL ret=;

     if (Block[p]==Block[q])

     {

         push_down(p);

         for (LL i=p;i<=q;i++) ret=(ret+a[i])%P;

         return ret;

     }

     for (LL i=Block[p]+;i<Block[q];i++) ret=(ret+tree[i].sum)%P;

     push_down(p),push_down(q);

     for (LL i=p;Block[i]==Block[p];i++) ret=(ret+a[i])%P;

     for (LL i=q;Block[i]==Block[q];i--) ret=(ret+a[i])%P;

     return ret;

 }

 int main()

 {

     scanf("%lld%lld",&n,&P);

     for (LL i=;i<=n;i++) scanf("%lld",&a[i]),a[i]%=P;

     LL pos=(LL)sqrt(n);

     for (LL i=;i<=n;i++) Block[i]=(i-)/pos+;

     memset(tree,,sizeof(tree));

     for (LL i=;i<=n;i++) tree[Block[i]].len++;

     for (LL i=;i<=n;i++) tree[Block[i]].mul=;

     for (LL i=;i<=n;i++) tree[Block[i]].sum=(tree[Block[i]].sum+a[i])%P;

     scanf("%lld",&m);

     for (LL i=;i<=m;i++)

     {

         scanf("%lld",&type);

         if (type==)

         {

             scanf("%lld%lld%lld",&l,&r,&c);

             Mul(l,r,c);

         }

         if (type==)

         {

             scanf("%lld%lld%lld",&l,&r,&c);

             Add(l,r,c);

         }

         if (type==)

         {

             scanf("%lld%lld",&l,&r);

             printf("%lld\n",Sum(l,r));

         }

     }

     return ;

 }