#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5;
struct tree {
	ll l,r,data_sum;
}tr[4*N+5];
ll n,p,a[N+5],m,op,t,g,c,mul_tag[4*N+5],add_tag[4*N+5],ans;
inline void build(ll l1,ll r1,ll k) {
	tr[k].l=l1;
	tr[k].r=r1;
	if(l1==r1) {
		tr[k].data_sum=a[l1]%p;
		return;
	}
	ll mid=(r1-l1)/2+l1;
	build(l1,mid,k*2);
	build(mid+1,r1,k*2+1);
	tr[k].data_sum=(tr[k*2].data_sum+tr[k*2+1].data_sum)%p;
}
inline void pushdown(ll k) {
	tr[k*2].data_sum=(tr[k*2].data_sum*mul_tag[k])%p;
	tr[k*2].data_sum=(tr[k*2].data_sum+add_tag[k])%p;
	tr[k*2+1].data_sum=(tr[k*2+1].data_sum*mul_tag[k])%p;
	tr[k*2+1].data_sum=(tr[k*2+1].data_sum+add_tag[k])%p;
	mul_tag[k*2]=(mul_tag[k*2]*mul_tag[k])%p;
	mul_tag[k*2+1]=(mul_tag[k*2+1]*mul_tag[k])%p;
	add_tag[k*2]=(add_tag[k*2]*mul_tag[k])%p;
	add_tag[k*2+1]=(add_tag[k*2+1]*mul_tag[k])%p;
	add_tag[k*2]=(add_tag[k*2]+add_tag[k])%p;
	add_tag[k*2+1]=(add_tag[k*2+1]+add_tag[k])%p;
	mul_tag[k]=1;
	add_tag[k]=0;
}
inline void mul(ll k,ll l1,ll r1) {
	if(tr[k].l>=l1&&tr[k].r<=r1) {
		tr[k].data_sum=(tr[k].data_sum*c)%p;
		mul_tag[k]=(mul_tag[k]*c)%p;
		add_tag[k]=(add_tag[k]*c)%p;
		return;
	}
	pushdown(k);
	ll mid=(tr[k].r-tr[k].l)/2+tr[k].l;
	if(t<=mid)
		mul(k*2,l1,r1);
	if(g>mid)
		mul(k*2+1,l1,r1);
	tr[k].data_sum=(tr[k*2].data_sum+tr[k*2+1].data_sum)%p;	
}
inline void add(ll k,ll l1,ll r1) {
	if(tr[k].l>=l1&&tr[k].r<=r1) {
		tr[k].data_sum=(tr[k].data_sum+((tr[k].r-tr[k].l+1)*c)%p)%p;
		add_tag[k]=(add_tag[k]+c)%p;
		return;
	}
	pushdown(k);
	ll mid=(tr[k].r-tr[k].l)/2+tr[k].l;
	if(t<=mid)
		add(k*2,l1,r1);
	if(g>mid)
		add(k*2+1,l1,r1);
	tr[k].data_sum=(tr[k*2].data_sum+tr[k*2+1].data_sum)%p;
}
inline void query(ll k,ll l1,ll r1) {
	if(tr[k].l>=l1&&tr[k].r<=r1) {
		ans=(ans+tr[k].data_sum)%p;
		return;
	}
	pushdown(k);
	ll mid=(tr[k].r-tr[k].l)/2+tr[k].l;
	if(t<=mid)
		query(k*2,l1,r1);
	if(g>mid)
		query(k*2+1,l1,r1);
	tr[k].data_sum=(tr[k*2].data_sum+tr[k*2+1].data_sum)%p;
}
int main() {
	scanf("%lld%lld",&n,&p);
	for(int i=1; i<=n; i++)
		scanf("%lld",&a[i]);
	build(1,n,1);
	scanf("%lld",&m);
	for(int i=0; i<4*N+5; i++)
		mul_tag[i]=1;
	for(int i=1; i<=m; i++) {
		scanf("%lld%lld%lld",&op,&t,&g);
		if(op==1) {
			scanf("%lld",&c);
			mul(1,t,g);
		} else if(op==2) {
			scanf("%lld",&c);
			add(1,t,g);
		} else {
			ans=0;
			query(1,t,g);
			printf("%lld\n",ans);
		}
	}
	return 0;
}