#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
using namespace std;
namespace Yorihime_Nao{
	template<class T> T MAX(T x,T y){
		return x>y?x:y;
	}
	template<class T,class ... Arg> T MAX(T x,T y,Arg ... arg){
		return MAX(x>y?x:y,arg...);
	}
	template<class T> T MIN(T x,T y){
		return x<y?x:y;
	}
	template<class T,class ... Arg> T MIN(T x,T y,Arg ... arg){
		return MIN(x<y?x:y,arg...);
	}
	template<class T> T lowbit(T x){
		return x&-x;
	}
}
using namespace Yorihime_Nao;
const ll MAXN=1e5+5;
ll n,p,q,arr[MAXN],op,l,r,x;
ll data[MAXN<<2],lazy_add[MAXN<<2],lazy_mul[MAXN<<2];
void build(ll id,ll L,ll R){
	if(L==R){
		data[id]=arr[L]%p;
		lazy_add[id]=0;
		lazy_mul[id]=1;
		return;
	}
	ll mid=L+R>>1;
	build(id<<1,L,mid);
	build((id<<1)+1,mid+1,R);
	data[id]=(data[id<<1]+data[(id<<1)+1])%p;
	return;
}
void push_down(ll id,ll L,ll R){
	ll mid=L+R>>1;
	data[id<<1]=(data[id<<1]*lazy_mul[id]%p+lazy_add[id]*(mid-L+1)%p)%p;
	lazy_add[id<<1]=(lazy_add[id<<1]*lazy_mul[id]%p+lazy_add[id])%p;
	lazy_mul[id<<1]=lazy_mul[id<<1]*lazy_mul[id]%p;
	data[(id<<1)+1]=(data[(id<<1)+1]*lazy_mul[id]%p+lazy_add[id]*(R-mid)%p)%p;
	lazy_add[(id<<1)+1]=(lazy_add[(id<<1)+1]*lazy_mul[id]%p+lazy_add[id])%p;
	lazy_mul[(id<<1)+1]=lazy_mul[(id<<1)+1]*lazy_mul[id]%p;
	lazy_add[id]=0;
	lazy_mul[id]=1;
	return;
}
void add(ll id,ll L,ll R,ll UL,ll UR,ll delta){
	if(L>UR||R<UL)return;
	if(UL<=L&&R<=UR){
		data[id]=(data[id]+(R-L+1)*delta%p)%p;
		lazy_add[id]=(lazy_add[id]+delta)%p;
		return;
	}
	push_down(id,L,R);
	ll mid=L+R>>1;
	add(id<<1,L,mid,UL,UR,delta);
	add((id<<1)+1,mid+1,R,UL,UR,delta);
	data[id]=(data[id<<1]+data[(id<<1)+1])%p;
	return;
}
void mul(ll id,ll L,ll R,ll UL,ll UR,ll delta){
	if(L>UR||R<UL)return;
	if(UL<=L&&R<=UR){
		data[id]=data[id]*delta%p;
		lazy_add[id]=lazy_mul[id]*delta%p;
		return;
	}
	push_down(id,L,R);
	ll mid=L+R>>1;
	mul(id<<1,L,mid,UL,UR,delta);
	mul((id<<1)+1,mid+1,R,UL,UR,delta);
	data[id]=(data[id<<1]+data[(id<<1)+1])%p;
	return;
}
ll query(ll id,ll L,ll R,ll QL,ll QR){
	if(L>QR||R<QL)return 0;
	if(QL<=L&&R<=QR)return data[id];
	push_down(id,L,R);
	ll mid=L+R>>1;
	return (query(id<<1,L,mid,QL,QR)+query((id<<1)+1,mid+1,R,QL,QR))%p;
}
int main(){
	scanf("%lld%lld",&n,&p);
	for(int i=1;i<=n;i++)scanf("%lld",&arr[i]);
	build(1,1,n);
	scanf("%lld",&q);
	for(int i=1;i<=q;i++){
		scanf("%lld%lld%lld",&op,&l,&r);
		if(op==1){
			scanf("%lld",&x);
			mul(1,1,n,l,r,x);
		}
		if(op==2){
			scanf("%lld",&x);
			add(1,1,n,l,r,x);
		}
		if(op==3)printf("%lld\n",query(1,1,n,l,r));
	}
	return 0;
}

0pts/dk