#include<iostream>
#include<cmath>
using namespace std;
long long op,x,y,k,n,m,b[114514],p;
struct tree{
    long long lazy2,lazy1,he;
    long long l,r;
}a[1919810];
long long build(long long jie,long long l,long long r){
    a[jie].lazy2=1,a[jie].l=l,a[jie].r=r;
    if(l==r)
        return a[jie].he=b[l];
    return a[jie].he=(build(jie*2,l,(l+r)/2)+build(jie*2+1,(l+r)/2+1,r))%p;
}
void push(long long jie){
    a[jie].lazy1%=p,
    a[jie].lazy2%=p,
    a[jie*2].lazy1%=p,
    a[jie*2].lazy2%=p,
    a[jie*2+1].lazy1%=p,
    a[jie*2+1].lazy2%=p,
    a[jie*2].lazy2=(a[jie].lazy2*a[jie*2].lazy2)%p,
    a[jie*2+1].lazy2=(a[jie].lazy2*a[jie*2+1].lazy2)%p,
    a[jie*2].lazy1*=a[jie].lazy2,
    a[jie*2+1].lazy1*=a[jie].lazy2,
    a[jie*2].lazy1+=a[jie].lazy1,
    a[jie*2+1].lazy1+=a[jie].lazy1,
    a[jie].he*=a[jie].lazy2;a[jie].he%=p,
    a[jie].he=(a[jie].he+a[jie].lazy1*(a[jie].r-a[jie].l+1))%p,
    a[jie].lazy2=1;a[jie].lazy1=0;
}
void add(long long jie,long long x,long long y,long long k){
    if(a[jie].r<x||a[jie].l>y)
        return ;
    if(a[jie].l>=x&&a[jie].r<=y)
        a[jie].lazy1=(k+a[jie].lazy1)%p;
    else{
        push(jie);
        add(jie*2,x,y,k);
        add(jie*2+1,x,y,k);
        a[jie].he=((min(a[jie].r,y)-max(a[jie].l,x)+1)*k+a[jie].he)%p;
    }
}
long long search(long long jie,long long x,long long y){
    push(jie);
    if(a[jie].r<x||a[jie].l>y)
        return 0;
    if(a[jie].l>=x&&a[jie].r<=y)
        return a[jie].he%p;
    return (search(jie*2,x,y)+search(jie*2+1,x,y))%p;
}
long long  read(){
    long long x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
void cheng(long long jie,long long x,long long y,long long k){
    if(a[jie].r<x||a[jie].l>y)
        return ;
    else if(a[jie].l>=x&&a[jie].r<=y)
        a[jie].lazy1=a[jie].lazy1*k%571373,a[jie].lazy2=a[jie].lazy2*k%p;
    else{
        a[jie].he+=search(1,max(a[jie].l,x),min(a[jie].r,y))*(k-1)%p;
		cheng(jie*2,x,y,k);
		cheng(jie*2+1,x,y,k);
    }
}
void write(long long x) {
  	static int sta[35];
  	int top = 0;
  	do {
	    sta[top++] = x % 10, x /= 10;
  	} while (x);
  	while (top) putchar(sta[--top] + 48);
	  putchar('\n');
}
int main(){
    n=read();p=read();
    for(int i=1;i<=n;i++)
        b[i]=read();
    build(1,1,n);m=read();
    while(m--){
        op=read();
        if(op==2){
            x=read(),
            y=read(),
            k=read(),
            add(1,x,y,k%p);
        }else if(op==3){
            x=read(),
            y=read(),
            write(search(1,x,y));
        }else if(op==1){
            x=read(),
            y=read(),
            k=read(),
            cheng(1,x,y,k%p);
        }
    }
}