#include <iostream>
#include <cstdio>

#define ll long long
#define MAXN 100005

using namespace std;

ll n, opt, t, g, c, p, m;
ll a[MAXN], tag_mul[MAXN*4], tag_add[MAXN*4], sum[MAXN*4];

inline ll ls(ll x){
	return x*2;
}

inline ll rs(ll x){
	return (x*2)+1;
}

void push_up(ll x){
	sum[x]=(sum[ls(x)]+sum[rs(x)])%p;
	return;
}

void build(ll x, ll l, ll r){
	if(l>r)return;
	
	if(l==r){
		sum[x]=a[l]%p;
		return;
	}
	
	ll mid=(l+r)/2;
	tag_add[x]=0, tag_mul[x]=1;
	build(ls(x), l, mid);
	build(rs(x), mid+1, r);
	push_up(x);
	return;
}

void push_down(ll x, ll l, ll r){
	ll mid=(l+r)/2;
	
	sum[ls(x)]=(sum[ls(x)]*tag_mul[x])%p;
	sum[ls(x)]=(sum[ls(x)]+(mid-l+1)*tag_add[x])%p;

	sum[rs(x)]=(sum[rs(x)]*tag_mul[x])%p;
	sum[rs(x)]=(sum[rs(x)]+(r-mid)*tag_add[x])%p;
	
	tag_mul[ls(x)]=(tag_mul[ls(x)]*tag_mul[x])%p;
	tag_mul[rs(x)]=(tag_mul[rs(x)]*tag_mul[x])%p;
	
	tag_add[ls(x)]=(tag_add[ls(x)]*tag_mul[x]+tag_add[ls(x)])%p;
	tag_add[rs(x)]=(tag_add[rs(x)]*tag_mul[x]+tag_add[rs(x)])%p;
	
	tag_add[x]=0, tag_mul[x]=1;
	return;
}

void add(ll x, ll l, ll r, ll L, ll R, ll k){
	if(l>r)return;

	if(L<=l&&r<=R){
		sum[x]=(sum[x]+(r-l+1)*k)%p;
		tag_add[x]=(tag_add[x]+k)%p;
		return;
	}
	
	push_down(x, l, r);
	
	ll mid=(l+r)/2;
	if(L<=mid)add(ls(x), l, mid, L, R, k);
	if(R>mid)add(rs(x), mid+1, r, L, R, k);
	
	push_up(x);
	
	return;
}

void mul(ll x, ll l, ll r, ll L, ll R, ll k){
	if(l>r)return;

	if(L<=l&&r<=R){
		sum[x]=(sum[x]*k)%p;
		tag_mul[x]=(tag_mul[x]*k)%p;
		tag_add[x]=(tag_add[x]*k)%p;
		return;
	}
	
	push_down(x, l, r);
	
	ll mid=(l+r)/2;
	if(L<=mid)mul(ls(x), l, mid, L, R, k);
	if(R>mid)mul(rs(x), mid+1, r, L, R, k);
	
	push_up(x);
	
	return;
}

ll query(ll x, ll l, ll r, ll L, ll R){
	if(l>r)return 0;
	
	if(L<=l&&r<=R)return sum[x];
	
	push_down(x, l, r);
	
	ll mid=(l+r)/2;
	ll ans=0;
	if(L<=mid)ans=(ans+query(ls(x),l,mid,L,R))%p;
	if(R>mid)ans=(ans+query(rs(x),mid+1,r,L,R))%p;
	
	return ans;
}

int main(){
	scanf("%lld%lld", &n, &p);
	for(ll i=1; i<=n; i++)scanf("%lld", &a[i]);
	build(1, 1, n);
	
	scanf("%lld", &m);
	for(ll i=1; i<=m; i++){
		scanf("%lld%lld%lld", &opt, &t, &g);
		if(opt==1){
			scanf("%lld", &c);
			mul(1, 1, n, t, g, c);
		}
		else if(opt==2){
			scanf("%lld", &c);
			add(1, 1, n, t, g, c);
		}
		else{ //opt==3
			printf("%lld\n", query(1, 1, n, t, g));
		}
	}
	
	return 0;
}