rt，这段代码在 P3373线段树模版2 上面 A 了，在这里过不去。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,q,a[1000010],sum[5000010],p,x,y,k,num[5000010],num2[5000010];
void pushdown(ll bh,ll ln,ll rn){
	sum[bh*2]=(sum[bh*2]*num2[bh]+num[bh]*ln)%q;
	sum[bh*2+1]=(sum[bh*2+1]*num2[bh]+num[bh]*rn)%q;
	num2[bh*2]=(num2[bh*2]*num2[bh])%q;
	num2[bh*2+1]=(num2[bh*2+1]*num2[bh])%q;
	num[bh*2]=(num[bh*2]*num2[bh]+num[bh])%q;
	num[bh*2+1]=(num[bh*2+1]*num2[bh]+num[bh])%q;	
	num[bh]=0;
	num2[bh]=1;
}
void build(ll l,ll r,ll bh){
	if(l==r){
		sum[bh]=a[l];
		return;
	}
	ll mid=(l+r)>>1;
	build(l,mid,bh*2);
	build(mid+1,r,bh*2+1);
	sum[bh]=(sum[bh*2]+sum[bh*2+1])%q;
	num2[bh]=1;
}
void add(ll L,ll R,ll l,ll r,ll k,ll bh){
	if(l<=L&&r>=R){
		sum[bh]=(sum[bh]+(R-L+1)*k)%q;
		num[bh]+=k;
		return;
	}
	ll mid=(L+R)>>1;
	pushdown(bh,mid-L+1,R-mid);
	if(l<=mid) add(L,mid,l,r,k,bh*2);
	if(r>mid) add(mid+1,R,l,r,k,bh*2+1);
	sum[bh]=(sum[bh*2]+sum[bh*2+1])%q;
}
void add2(ll L,ll R,ll l,ll r,ll k,ll bh){
	if(l<=L&&r>=R){
		sum[bh]=(sum[bh]*k)%q;
		num2[bh]*=k;
		num[bh]*=k;
		return;
	}
	ll mid=(L+R)>>1;
	pushdown(bh,mid-L+1,R-mid);
	if(l<=mid) add2(L,mid,l,r,k,bh*2);
	if(r>mid) add2(mid+1,R,l,r,k,bh*2+1);
	sum[bh]=(sum[bh*2]+sum[bh*2+1])%q;
}
ll find(ll L,ll R,ll l,ll r,ll bh){
	if(l<=L&&r>=R){
		return sum[bh];
	}
	ll mid=(L+R)>>1;
	pushdown(bh,mid-L+1,R-mid);
	ll ans=0;
	if(l<=mid) ans+=find(L,mid,l,r,bh*2);
	ans%=q;
	if(r>mid) ans+=find(mid+1,R,l,r,bh*2+1);
	return ans%q;
}
int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,n,1);
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>p>>x>>y;
		if(p==1){
			cin>>k;
			add2(1,n,x,y,k,1);
		}
		else if(p==2){
			cin>>k;
			add(1,n,x,y,k,1);
		}
		else cout<<find(1,n,x,y,1)%q<<endl;
	}
    return 0;
}