#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define C 350
#define int long long
int n,mod,a[N],m,op,x,y,z;
int len,c,st[C],ed[C],bl[N],sum[C],add[C],mul[C];
void init(){
	len=sqrt(n);
	c=(n-1)/len+1;
	for(int i=1;i<=c;i++){
		st[i]=ed[i-1]+1;
		ed[i]=i*len;
		mul[i]=1;
	}
	ed[c]=n;
	for(int i=1;i<=c;i++){
		for(int j=st[i];j<=ed[i];j++){
			bl[j]=i;
			sum[i]+=(sum[i]+a[j])%mod;
		}
	}
}
void ref(int p){
	for(int i=st[p];i<=ed[p];i++)
		a[i]=(a[i]*mul[p]+add[p])%mod;
	mul[p]=1;add[p]=0;
}
void edit1(int l,int r,int k){
	int p=bl[l],q=bl[r];
	if(p==q){
		ref(p);
		for(int i=l;i<=r;i++){
			sum[p]-=a[i];
			a[i]=(a[i]*k)%mod;
			sum[p]=(sum[p]+a[i])%mod;
		}
	}
	else{
		for(int i=p+1;i<=q-1;i++){
			mul[i]=(mul[i]*k)%mod;
			add[i]=(add[i]*k)%mod;
			sum[i]=(sum[i]*k)%mod;
		}
		ref(p);ref(q);
		for(int i=l;i<=ed[p];i++){
			sum[p]-=a[i];
			a[i]=(a[i]*k)%mod;
			sum[p]=(sum[p]+a[i])%mod;
		}
		for(int i=st[q];i<=r;i++){
			sum[q]-=a[i];
			a[i]=(a[i]*k)%mod;
			sum[q]=(sum[q]+a[i])%mod;
		}
	}
}
void edit2(int l,int r,int k){
	int p=bl[l],q=bl[r];
	if(p==q){
		ref(p);
		for(int i=l;i<=r;i++){
			sum[p]-=a[i];
			a[i]=(a[i]+k)%mod;
			sum[p]=(sum[p]+a[i])%mod;
		}
	}
	else{
		for(int i=p+1;i<=q-1;i++){
			sum[i]=(sum[i]+k*(ed[i]-st[i]+1))%mod;
			add[i]=(add[i]+k)%mod;
		}
		ref(p);ref(q);
		for(int i=l;i<=ed[p];i++){
			sum[p]-=a[i];
			a[i]=(a[i]+k)%mod;
			sum[p]=(sum[p]+a[i])%mod;
		}
		for(int i=st[q];i<=r;i++){
			sum[q]-=a[i];
			a[i]=(a[i]+k)%mod;
			sum[q]=(sum[q]+a[i])%mod;
		}
	}
}
int ask(int l,int r){
	int ans=0,p=bl[l],q=bl[r];
	if(p==q){
		for(int i=l;i<=r;i++)
			ans=(ans+(a[i]*mul[p]+add[p]))%mod;
	}
	else{
		for(int i=p+1;i<=q-1;i++)
			ans=(ans+sum[i])%mod;
		for(int i=l;i<=ed[p];i++)
			ans=(ans+(a[i]*mul[p]+add[p]))%mod;
		for(int i=st[q];i<=r;i++)
			ans=(ans+(a[i]*mul[q]+add[q]))%mod;
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>mod;
	for(int i=1;i<=n;i++)cin>>a[i];
	init();
	cin>>m;
	while(m--){
		cin>>op>>x>>y;
		if(op==1){
			cin>>z;
			edit1(x,y,z);
		}
		if(op==2){
			cin>>z;
			edit2(x,y,z);
		}
		if(op==3){
			cout<<ask(x,y)<<"\n";
		}
	}
	return 0;
}
```\
人麻了啊啊啊啊啊