#include<cstdio>

 #include<cctype>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 using namespace std;

 #define ll long long

 #define maxn 100001

 #define root 1

 #define _left <<1

 #define _right <<1|1

 int n,m;

 ll mod;

 inline int getint() {

     char ch;

     while(!isdigit(ch=getchar()));

     int x=ch^'';

     while(isdigit(ch=getchar())) x=((x+(x<<))<<)+(ch^'');

     return x;

 }

 inline ll getll() {

     char ch;

     while(!isdigit(ch=getchar()));

     ll x=ch^'';

     while(isdigit(ch=getchar())) x=((x+(x<<))<<)+(ch^'');

     return x;

 }

 struct SegmentTree {

     ll val[maxn<<],add[maxn<<],mul[maxn<<];

     void push_up(const int p) {

         val[p]=(val[p _left]+val[p _right])%mod;

     }

     void build(const int p,const int b,const int e) {

         mul[p]=;

         add[p]=;

         if(b==e) {

             val[p]=getll()%mod;

             return;

         }

         int mid=(b+e)>>;

         build(p _left,b,mid);

         build(p _right,mid+,e);

         push_up(p);

     }

     int length(const int b,const int e) {

         return e-b+;

     }

     void push_down(const int p,const int b,const int e) {

         if(mul[p]!=) {

             val[p _left]=val[p _left]*mul[p]%mod;

             val[p _right]=val[p _right]*mul[p]%mod;

             mul[p _left]=mul[p _left]*mul[p]%mod;

             mul[p _right]=mul[p _right]*mul[p]%mod;

             add[p _left]=add[p _left]*mul[p]%mod;

             add[p _right]=add[p _right]*mul[p]%mod;

             mul[p]=;

         }

         if(add[p]) {

             int mid=(b+e)>>;

             val[p _left]=(val[p _left]+add[p]*length(b,mid))%mod;

             val[p _right]=(val[p _right]+add[p]*length(mid+,e))%mod;

             add[p _left]=(add[p _left]+add[p])%mod;

             add[p _right]=(add[p _right]+add[p])%mod;

             add[p]=;

         }

     }

     void modify_mul(const int p,const int b,const int e,const int l,const int r,const ll x) {

         if((b==l)&&(e==r)) {

             val[p]=val[p]*x%mod;

             mul[p]=mul[p]*x%mod;

             add[p]=add[p]*x%mod;

             return;

         }

         push_down(p,b,e);

         int mid=(b+e)>>;

         if(l<=mid) modify_mul(p _left,b,mid,l,min(mid,r),x);

         if(r>mid) modify_mul(p _right,mid+,e,max(mid+,l),r,x);

         push_up(p);

     }

     void modify_add(const int p,const int b,const int e,const int l,const int r,const ll x) {

         if((b==l)&&(e==r)) {

             val[p]=(val[p]+x*length(b,e))%mod;

             add[p]=(add[p]+x)%mod;

             return;

         }

         push_down(p,b,e);

         int mid=(b+e)>>;

         if(l<=mid) modify_add(p _left,b,mid,l,min(mid,r),x);

         if(r>mid) modify_add(p _right,mid+,e,max(mid+,l),r,x);

         push_up(p);

     }

     ll query(const int p,const int b,const int e,const int l,const int r) {

         if((b==l)&&(e==r)) {

             return val[p];

         }

         int mid=(b+e)>>;

         ll ans=;

         push_down(p,b,e);

         if(l<=mid) ans=(ans+query(p _left,b,mid,l,min(mid,r)))%mod;

         if(r>mid) ans=(ans+query(p _right,mid+,e,max(mid+,l),r))%mod;

         return ans;

     }

 };

 SegmentTree tree;

 int main() {

     n=getint();

     mod=getll();

     tree.build(root,,n);

     m=getint();

     while(m--) {

         int op=getint(),x=getint(),y=getint();

         if(op==) {

             ll k=getll()%mod;

             tree.modify_mul(root,,n,x,y,k);

             continue;

         }

         if(op==) {

             ll k=getll()%mod;

             tree.modify_add(root,,n,x,y,k);

             continue;

         }

         printf("%lld\n",tree.query(root,,n,x,y));

     }

     return ;

 }