#include<bits/stdc++.h>
#define lc x<<1
#define rc x<<1|1
#define int long long
using namespace std;
int n,q,mod,op,l,r,k,a[100005];
struct node{
	int l,r,val,lazya=0,lazyq=1;
} tr[400005];
void pushup(int x){
	tr[x].val=tr[lc].val%mod+tr[rc].val%mod;
}
void maketaga(int x,int k){
	tr[x].lazya+=(k%mod);
	tr[x].val+=(k*(tr[x].r-tr[x].l+1))%mod;
}
void maketagq(int x,int k){
	k%=mod;
	tr[x].lazya*=k;
	tr[x].lazya%=mod;
	tr[x].lazyq*=k;
	tr[x].lazyq%=mod;
	tr[x].val*=k;
	tr[x].val%=mod;
}
void pushdown(int x){
	maketagq(lc,tr[x].lazyq%mod);
	maketaga(lc,tr[x].lazya%mod);
	maketagq(rc,tr[x].lazyq%mod);
	maketaga(rc,tr[x].lazya%mod);
	tr[x].lazyq=1;tr[x].lazya=0;
	return ;
}
void build(int x,int l,int r){
	tr[x].l=l;tr[x].r=r;
	if(l==r){
		tr[x].val=a[l]%mod;
		return ;
	}
	int mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(x);
}
void update(int x,int l,int r,int k){
	if(l<=tr[x].l and tr[x].r<=r){
		maketaga(x,k%mod);
		return ;
	}
	int mid=(tr[x].l+tr[x].r)>>1;
	if(l<=mid)	update(lc,l,r,k);
	if(mid<r)   update(rc,l,r,k);
	pushup(x);
	pushdown(x);
	pushup(x);
}
void update1(int x,int l,int r,int k){
	if(l<=tr[x].l and tr[x].r<=r){
		maketagq(x,k%mod);
		return ;
	}
	int mid=(tr[x].l+tr[x].r)>>1;
	if(l<=mid)	update1(lc,l,r,k);
	if(mid<r)   update1(rc,l,r,k);
	pushup(x);
	pushdown(x);
	pushup(x);
}
int query(int x,int l,int r){
	if(l<=tr[x].l and tr[x].r<=r){
	 	return tr[x].val;
	}
	pushdown(x);
	pushup(x);
	int mid=(tr[x].l+tr[x].r)>>1,sum=0;
	if(l<=mid) sum+=query(lc,l,r);
	if(mid<r)  sum+=query(rc,l,r);
	return sum;
}
void prf(){
	for(int i=1;i<=n;i++){
		cout<<query(1,i,i)<<" ";
	}
	cout<<"\n";
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>mod;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	cin>>q;
	for(int i=1;i<=q;i++){
		cin>>op;
		if(op==2){
			cin>>l>>r>>k;
			update(1,l,r,k%mod);
		}else if(op==1){
			cin>>l>>r>>k;
			update1(1,l,r,k%mod);
		}else if(op==3){
			cin>>l>>r;
			cout<<query(1,l,r)%mod<<"\n";
		}
	}
	return 0;
}