#include<cstdio>
#include<algorithm>
#include<iostream>
#define N 400005
#define lc p<<1
#define rc p<<1|1
#define int long long
#define m (l+r)/2
#define mid (s[p].l+s[p].r)/2
using namespace std;
struct linetree{
	int l,r,sum;
	int add,mlt;
}s[N];
int n,mo,tt;
void pushup(int p){
	s[p].sum=(s[lc].sum+s[rc].sum)%mo;
}
void build(int p,int l,int r){
	s[p].l=l,s[p].r=r;
	if(l==r){
		int a=0;scanf("%lld",&a);
		s[p].sum=a;
		s[p].add=0;
		s[p].mlt=1;
		return;
	}
	build(lc,l,m);
	build(rc,m+1,r);
	pushup(p);
}
void pushdown(int p){
	s[lc].sum=((s[lc].sum*s[p].mlt)%mo+((s[lc].r-s[lc].l+1)*s[p].add)%mo)%mo;
	s[rc].sum=((s[rc].sum*s[p].mlt)%mo+((s[rc].r-s[rc].l+1)*s[p].add)%mo)%mo;
	s[lc].add=((s[p].mlt*s[lc].add)%mo+s[p].add)%mo;
	s[rc].add=((s[p].mlt*s[rc].add)%mo+s[p].add)%mo;
	s[lc].mlt=(s[lc].mlt*s[p].mlt)%mo;
	s[rc].mlt=(s[rc].mlt*s[p].mlt)%mo;
	s[p].mlt=1,s[p].add=0;
}
void mul(int p,int l,int r,int c){
	pushdown(p);
	if(s[p].l>r||s[p].r<l)return;
	if(s[p].l>=l||s[p].r<=r){
		s[p].mlt=(s[p].mlt*c)%mo;
		s[p].add=(s[p].add*c)%mo;
		s[p].sum=(s[p].sum*c)%mo;
		return;
	}
	if(mid>=l)mul(lc,l,r,c);
	if(mid<r)mul(rc,l,r,c);
	pushup(p);
}
void pluss(int p,int l,int r,int c){
	pushdown(p);
	if(s[p].l>r||s[p].r<l)return;
	if(s[p].l>=l||s[p].r<=r){
		s[p].add=(s[p].add+c)%mo;
		s[p].sum=(s[p].sum+((s[p].r-s[p].l+1)*c)%mo)%mo;
		return;
	}
	if(mid>=l)pluss(lc,l,r,c);
	if(mid<r)pluss(rc,l,r,c);
	pushup(p);
}
int query(int p,int l,int r){
	pushdown(p);
	if(s[p].l>r||s[p].r<l)return 0;
	if(s[p].l>=l||s[p].r<=r)return s[p].sum%mo;	
	int ans=0;
	if(mid>=l)ans+=query(lc,l,r);
	if(mid<r)ans+=query(rc,l,r); 
	return ans%mo;
}
signed main(){
	scanf("%lld%lld",&n,&mo);
	build(1,1,n);
	scanf("%lld",&tt);
	for(int i=1;i<=tt;i++){
		int op,t,g,c;
		cin>>c>>t>>g;
		if(op==1){
			cin>>c;mul(1,t,g,c);
		}
		if(op==2){
			cin>>c;pluss(1,t,g,c);
		}
		else printf("%lld\n",query(1,t,g));
	}
	return 0;
}