[模板]线段树1/2已过

#include <bits/stdc++.h>
using namespace std;
long long d[400010],lazy[400010],lazyx[400010],c=0;
long long a[400010];
long long a1,b1,c1,d1;
long long n,m,mod;
void pre(long long p,long long s,long long t,long long x,long long l,long long r){
	if(lazyx[p]!=1&&s!=t){
		d[p*2]*=lazyx[p]%mod;
		d[p*2]%=mod;
		lazy[p*2]*=lazyx[p]%mod;
		lazy[p*2]%=mod;
		d[p*2+1]*=lazyx[p]%mod;
		d[p*2+1]%=mod;
		lazy[p*2+1]*=lazyx[p]%mod;
		lazy[p*2+1]%=mod;
		lazyx[p*2]*=lazyx[p]%mod;
		lazyx[p*2]%=mod;
		lazyx[p*2+1]*=lazyx[p]%mod;
		lazyx[p*2+1]%=mod;
		lazyx[p]=1;
	}
	if(lazy[p]!=0&&s!=t){
		d[p*2]+=(x-l+1)*lazy[p];
		d[p*2]%=mod;
		lazy[p*2]+=lazy[p]%mod;
		lazy[p*2]%=mod;
		d[p*2+1]+=(r-x)*lazy[p]%mod;
		lazy[p*2+1]+=lazy[p]%mod;
		lazy[p]=0;
		d[p*2+1]%=mod;
		lazy[p*2+1]%=mod;
	}
}
void chen(long long s,long long t,long long l,long long r,long long p){
	if(l>=s&&r<=t){
		d[p]*=d1%mod;
		d[p]%=mod;
		lazy[p]*=d1%mod;
		lazy[p]%=mod;
		lazyx[p]*=d1%mod;
		lazyx[p]%=mod;
		return;
	}
	long long x=l+((r-l)>>1);
	pre(p,s,t,x,l,r);
	if(s<=x){
		chen(s,t,l,x,p*2);
	}
	if(t>x){
		chen(s,t,x+1,r,p*2+1);
	}
	d[p]=(d[p*2]+d[p*2+1])%mod;
}
long long find(long long s,long long t,long long l,long long r,long long p){
	if(l>=s&&r<=t){
		return d[p];
	}
	long long x=l+((r-l)>>1);
	pre(p,s,t,x,l,r);
	long long sum=0;
	if(s<=x){
		sum+=find(s,t,l,x,p*2)%mod;
		sum=sum%mod;
	}
	if(t>x){
		sum+=find(s,t,x+1,r,p*2+1)%mod;
		sum=sum%mod; 
	}
	return sum;
}
void add(long long s,long long t,long long l,long long r,long long p){
	if(l>=s&&r<=t){
		d[p]+=(r-l+1)*d1%mod;
        d[p]%=mod;
		lazy[p]+=d1;
        lazy[p]%=mod;
		return;
	}
	long long x=l+((r-l)>>1%mod);
	pre(p,s,t,x,l,r);
	if(s<=x){
		add(s,t,l,x,p*2);
	}
	if(t>x){
		add(s,t,x+1,r,p*2+1);
	}
	d[p]=(d[p*2]+d[p*2+1])%mod;
}
void build(long long s,long long e,long long p){
	lazyx[p]=1;
	if(s==e){
		d[p]=a[s];
		return;
	}
	long long x=s+((e-s)>>1);
	build(s,x,p*2);
	build(x+1,e,p*2+1);
	d[p]=(d[p*2]+d[p*2+1])%mod;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%lld%lld",&n,&mod);
	for(long long i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		c+=a[i];
	}
	d[1]=c;
	build(1,n,1);
    cin>>m;
	for(long long i=1;i<=m;i++){
		int o=1,k=0;
		scanf("%lld%lld%lld",&a1,&b1,&c1);
		if(a1==1){
			scanf("%lld",&d1);
			chen(b1,c1,1,n,1);
		}
		if(a1==2){
			scanf("%lld",&d1);
			add(b1,c1,1,n,1);
		}
		if(a1==3){
			printf("%lld\n",find(b1,c1,1,n,1)%mod);
		}
		o=1,k=0;
	}
	return 0;
}