样例过了，测试全wa

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define N 200005
struct nod{
	int l,r,add,sum,mul;
}t[N<<2];
int n,m,mod,a[N];
inline void build(int l,int r,int p){
	t[p].l=l,t[p].r=r,t[p].mul=1;
	if(l==r){
		t[p].sum=a[l]%mod;
		return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	build(l,mid,p<<1);
	build(mid+1,r,p<<1|1);
	t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%mod;
}
inline void spread(int p){
	if(t[p].add){
		t[p<<1].sum=(t[p].mul*t[p<<1].sum)%mod+(t[p].add*(t[p<<1].r-t[p<<1].l+1))%mod;
		t[p<<1].sum%=mod;
		t[p<<1|1].sum=(t[p].mul*t[p<<1|1].sum)%mod+(t[p].add*(t[p<<1|1].r-t[p<<1|1].l+1))%mod;
		t[p<<1|1].sum%=mod;
		
		t[p<<1].add=t[p].add+(t[p].mul*t[p<<1].add)%mod;
		t[p<<1].add%=mod;
		t[p<<1|1].add=t[p].add+(t[p].mul*t[p<<1|1].add)%mod;
		t[p<<1|1].add%=mod;
		
		t[p<<1].mul=(t[p].mul*t[p<<1].mul)%mod;
		t[p<<1|1].mul=(t[p].mul*t[p<<1|1].mul)%mod;
		
		t[p].add=0;
		t[p].mul=1;
	}
}
inline void change_mul(int l,int r,int k,int p){
	if(l<=t[p].l&&t[p].r<=r){
		t[p].add=(t[p].add*k)%mod;
		t[p].mul=(t[p].mul*k)%mod;
		t[p].sum=(t[p].sum*k)%mod;
		return;
	}
	spread(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)change_mul(l,r,k,p<<1);
	if(mid<r)change_mul(l,r,k,p<<1|1);
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
	t[p].sum%=mod;
}
inline void change_add(int l,int r,int k,int p){
	if(l<=t[p].l&&t[p].r<=r){
		t[p].add=(t[p].add+k)%mod;
		t[p].sum=(t[p].sum+k*(t[p].r-t[p].l+1))%mod;
		return;
	}
	spread(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)change_add(l,r,k,p<<1);
	if(mid<r)change_add(l,r,k,p<<1|1);
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
	t[p].sum%=mod;
}
inline int getsum(int l,int r,int p){
	if(l<=t[p].l&&t[p].r<=r){
		return t[p].sum%mod;
	}
	spread(p);
	int ans=0;
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)ans=(ans+getsum(l,r,p<<1))%mod;
	if(mid<r)ans=(ans+getsum(l,r,p<<1|1))%mod;
	return ans%mod;
}
signed main(){
	scanf("%lld%lld",&n,&mod);
	for(re int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		a[i]%=mod;
	}
	scanf("%lld",&m);
	build(1,n,1);
	while(m--){
		int op;
		scanf("%lld",&op);
		if(op==1){
			int x,y,k;
			scanf("%lld%lld%lld",&x,&y,&k);
			change_mul(x,y,k,1);
		}else if(op==2){
			int x,y,k;
			scanf("%lld%lld%lld",&x,&y,&k);
			change_add(x,y,k,1);
		}else if(op==3){
			int x,y;
			scanf("%lld%lld",&x,&y);
			printf("%lld\n",getsum(x,y,1));
		}
	}
	return 0;
}