#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll d[400010],a[400010],mo,b[400010],bb[400010];
void build(ll l,ll r,ll p){
	if(l==r){
		d[p]=a[l];
		return;
	}
	ll m=l+(r-l)/2;
	build(l,m,p*2);
	build(m+1,r,p*2+1);
	d[p]=d[p*2]+d[p*2+1];
	d[p]%=mo;
}//建树
void sp(ll l,ll r,ll p){
	ll m=l+(r-l)/2;
	if(bb[p]!=1){
		bb[p*2]*=bb[p];bb[p*2]%=mo;
		bb[p*2+1]*=bb[p];bb[p*2+1]%=mo;
		b[p*2]*=bb[p];b[p*2]%=mo;
		b[p*2+1]*=bb[p];b[p*2+1]%=mo;
		d[p*2]*=bb[p];d[p*2]%=mo;
		d[p*2+1]*=bb[p];d[p*2+1]%=mo;
	}bb[p]=1;
	if(b[p]){
		b[p*2]+=b[p];b[p*2+1]+=b[p];
		b[p*2]%=mo;b[p*2+1]%=mo;
		d[p*2]+=b[p]*(m-l+1);d[p*2]%=mo;
		d[p*2+1]+=b[p]*(r-m);d[p*2+1]%=mo;
	}b[p]=0;
	return;
}//释放标记；
void updatea(ll l,ll r,ll c,ll s,ll t,ll p){
	if(s>=l&&t<=r){
		d[p]+=c*(t-s+1);d[p]%=mo;
		b[p]+=c;b[p]%=mo;
		return;
	}
	sp(s,t,p);
	ll m=s+(t-s)/2;
	if(l<=m)updatea(l,r,c,s,m,p*2);
	if(r>m)updatea(l,r,c,m+1,t,p*2+1);
	d[p]=d[p*2]+d[p*2+1];
	d[p]%=mo;
}//区间加；
void updatec(ll l,ll r,ll c,ll s,ll t,ll p){
	if(s>=l&&t<=r){
		d[p]*=c;d[p]%=mo;
		b[p]*=c;b[p]%=mo;
		bb[p]*=c;bb[p]%=mo;
		return;
	}
	sp(s,t,p);
	ll m=s+(t-s)/2;
	if(l<=m)updatec(l,r,c,s,m,p*2);
	if(r>m)updatec(l,r,c,m+1,t,p*2+1);
	d[p]=d[p*2]+d[p*2+1];
	d[p]%=mo;
}//区间乘；
ll getsum(ll l,ll r,ll s,ll t,ll p){
	if(s>=l&&t<=r){
		d[p]%=mo;
		return d[p];
	}
	ll m=s+(t-s)/2;
	ll sum=0;
	sp(s,t,p);
	if(l<=m)sum+=getsum(l,r,s,m,p*2);
	if(r>m)sum+=getsum(l,r,m+1,t,p*2+1);
	sum%=mo;
	return sum;
}//求和
ll n,q,op,x,y,k;
ll ans;
int main(){
	cin>>n>>mo;
	for(int i=1;i<=n;i++){
		bb[i]=1;
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,n,1);
	cin>>q;
	for(int i=0;i<q;i++){
		cin>>op>>x>>y;
		if(op==1){
			cin>>k;
			updatec(x,y,k,1,n,1);
		}
		if(op==2){
			cin>>k;
			updatea(x,y,k,1,n,1);
		}
		if(op==3){
			cout<<getsum(x,y,1,n,1)%mo<<endl;
		}
	}
	return 0;
}