分块，只过了第一个点

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
    char ch=getchar();
    int r=0,w=1;
    while(ch<'0'||ch>'9') w=ch=='-'?-1:w,ch=getchar();
    while(ch>='0'&&ch<='9') r=r*10+ch-'0',ch=getchar();
    return r*w;
}
void write(int n){
    if(n<0) putchar('-'),n*=-1;
    if(n>9) write(n/10);
    putchar(n % 10 + '0');
}
int n,m,p,s,l,r,k,cnt;
int xl[100001],xg[100001],cf[100001],ans[100001];
int x[100001],y[100001],fk[100001];
signed main(){
	n=read(),p=read();
	for(int i=1;i<=(int)sqrt(n);i++){
		cnt++;
		x[cnt]=y[cnt-1]+1;
		y[cnt]=x[cnt]+(int)sqrt(n)-1;
		for(int j=x[cnt];j<=y[cnt];j++){
			fk[j]=cnt;
		}
	}
	if(y[cnt]<n){
		cnt++;
		x[cnt]=y[cnt-1]+1;
		y[cnt]=n;
		for(int i=x[cnt];i<=y[cnt];i++){
			fk[i]=cnt;
		}
	}
	for(int i=1;i<=cnt;i++){
		cf[i]=1;
	}
	for(int i=1;i<=n;i++){
		xl[i]=read();
		ans[fk[i]]=(ans[fk[i]]+xl[i])%p;
	}
	m=read();
	for(int i=1;i<=m;i++){
		s=read();
		if(s==1){
			l=read(),r=read(),k=read();
			ans[fk[l]]=0;
			for(int j=l;j<=min(r,y[fk[l]]);j++){
				xl[j]=((xl[j]*cf[fk[l]]+xg[fk[l]])%p*k)%p;
				ans[fk[l]]=(ans[fk[l]]+x[j])%p;
			}
			for(int j=x[fk[l]];j<l;j++){
				xl[j]=(xl[j]*cf[fk[l]]+xg[fk[l]])%p;
				ans[fk[l]]=(ans[fk[l]]+x[j])%p;
			}
			if(r<y[fk[l]]){
				for(int j=r+1;j<=y[fk[l]];j++){
					xl[j]=(xl[j]*cf[fk[l]]+xg[fk[l]])%p;
					ans[fk[l]]=(ans[fk[l]]+x[j])%p;
				}
			}
			xg[fk[l]]=0,cf[fk[l]]=1;
			if(fk[l]!=fk[r]){
				ans[fk[r]]=0;
				for(int j=x[fk[r]];j<=r;j++){
					xl[j]=((xl[j]*cf[fk[r]]+xg[fk[r]])%p*k)%p;
					ans[fk[r]]=(ans[fk[r]]+x[j])%p;
				}
				for(int j=r+1;j<=y[fk[r]];j++){
					xl[j]=(xl[j]*cf[fk[r]]+xg[fk[r]])%p;
					ans[fk[r]]=(ans[fk[r]]+x[j])%p;
				}
				xg[fk[r]]=0,cf[fk[r]]=1;
			}
			for(int j=fk[l]+1;j<fk[r];j++){
				xg[j]=(xg[j]*k)%p;
				cf[j]=(cf[j]*k)%p;
				ans[j]=(ans[j]*k)%p;
			}
		}
		else if(s==2){
			l=read(),r=read(),k=read();
			ans[fk[l]]=0;
			for(int j=l;j<=min(r,y[fk[l]]);j++){
				xl[j]=((xl[j]*cf[fk[l]]+xg[fk[l]])+k)%p;
				ans[fk[l]]=(ans[fk[l]]+x[j])%p;
			}
			for(int j=x[fk[l]];j<l;j++){
				xl[j]=(xl[j]*cf[fk[l]]+xg[fk[l]])%p;
				ans[fk[l]]=(ans[fk[l]]+x[j])%p;
			}
			if(r<y[fk[l]]){
				for(int j=r+1;j<=y[fk[l]];j++){
					xl[j]=(xl[j]*cf[fk[l]]+xg[fk[l]])%p;
					ans[fk[l]]=(ans[fk[l]]+x[j])%p;
				}
			}
			xg[fk[l]]=0,cf[fk[l]]=1;
			if(fk[l]!=fk[r]){
				ans[fk[r]]=0;
				for(int j=x[fk[r]];j<=r;j++){
					xl[j]=((xl[j]*cf[fk[r]]+xg[fk[r]])+k)%p;
					ans[fk[r]]=(ans[fk[r]]+x[j])%p;
				}
				for(int j=r+1;j<=y[fk[r]];j++){
					xl[j]=(xl[j]*cf[fk[r]]+xg[fk[r]])%p;
					ans[fk[r]]=(ans[fk[r]]+x[j])%p;
				}
				xg[fk[r]]=0,cf[fk[r]]=1;
			}
			for(int j=fk[l]+1;j<fk[r];j++){
				xg[j]=(xg[j]+k)%p;
				ans[j]=(ans[j]+(y[j]-x[j]+1)*k%p)%p;
			}
		}
		else{
			l=read(),r=read();
			cnt=0;
			for(int j=l;j<=min(r,y[fk[l]]);j++){
				cnt=(cnt+xl[j]*cf[fk[l]]+xg[fk[l]])%p;
			}
			if(fk[l]!=fk[r]){
				for(int j=x[fk[r]];j<=r;j++){
					cnt=(cnt+xl[j]*cf[fk[r]]+xg[fk[r]])%p;
				}
			}
			for(int j=fk[l]+1;j<fk[r];j++){
				cnt=(cnt+ans[j])%p;
			}
			write(cnt);
			printf("\n");
		}
	}
	return 0;
}