#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

using namespace std;

int read(){

    int s=,t=;char c;

    while(!isdigit(c=getchar()))if(c=='-')t=-;

    do{s=s*+c-'';}while(isdigit(c=getchar()));

    return s*t;

}

const int maxn=;

struct tree{int l,r,a,b,sum;}t[maxn*];

int n,MOD,a[maxn];

int M(int x){return x>=MOD?x-MOD:x;}

void up(int k){t[k].sum=M(t[k<<].sum+t[k<<|].sum);}

void modify_a(int k,int x){t[k].sum=M(t[k].sum+1ll*(t[k].r-t[k].l+)*x%MOD);t[k].a=M(t[k].a+x);}//

void modify_b(int k,int x){t[k].sum=1ll*t[k].sum*x%MOD;t[k].b=1ll*t[k].b*x%MOD;t[k].a=1ll*t[k].a*x%MOD;}

void down(int k){

    if(t[k].b!=){//

        modify_b(k<<,t[k].b);modify_b(k<<|,t[k].b);

        t[k].b=;

    }

    if(t[k].a){

        modify_a(k<<,t[k].a);modify_a(k<<|,t[k].a);

        t[k].a=;

    }

}

void build(int k,int l,int r){

    t[k].l=l;t[k].r=r;t[k].a=;t[k].b=;

    if(l==r){t[k].sum=a[l];return;}

    int mid=(l+r)>>;

    build(k<<,l,mid);build(k<<|,mid+,r);

    up(k);

}

void add(int k,int l,int r,int x){

    if(l<=t[k].l&&t[k].r<=r){modify_a(k,x);return;}

    down(k);

    int mid=(t[k].l+t[k].r)>>;//

    if(l<=mid)add(k<<,l,r,x);

    if(r>mid)add(k<<|,l,r,x);

    up(k);

}

void mul(int k,int l,int r,int x){

    if(l<=t[k].l&&t[k].r<=r){modify_b(k,x);return;}

    down(k);

    int mid=(t[k].l+t[k].r)>>;//

    if(l<=mid)mul(k<<,l,r,x);

    if(r>mid)mul(k<<|,l,r,x);

    up(k);

}

int query(int k,int l,int r){

    if(l<=t[k].l&&t[k].r<=r){return t[k].sum;}

    down(k);

    int mid=(t[k].l+t[k].r)>>,sum=;

    if(l<=mid)sum=query(k<<,l,r);

    if(r>mid)sum=M(sum+query(k<<|,l,r));

    return sum;

}

int main(){

    n=read();MOD=read();

    for(int i=;i<=n;i++)a[i]=read()%MOD;

    build(,,n);

    int m=read();

    while(m--){

        int k=read(),x=read(),y=read();

        if(k==){printf("%d\n",query(,x,y));continue;}

        int z=read();

        if(k==)mul(,x,y,z%MOD);else add(,x,y,z%MOD);

    }

    return ;

}