#include<bits/stdc++.h>
#define N 110000
//#define int long long
using namespace std;
int mod;
int a[N],sum[N<<2],lazya[N<<2],lazyb[N<<2];
void build(int L,int R,int id) {
	int mid=(L+R)/2;
	lazya[id]=1;
	if(L==R) sum[id] = lazyb[id] = a[L];
	else build(L,mid,id<<1) , build(mid+1,R,id<<1|1) , sum[id] = (sum[id<<1] + sum[id<<1|1]) % mod;
}
void upd(int id,int L,int R) {
	sum[id] = ((sum[id<<1]+sum[id<<1|1])*lazya[id]+lazyb[id]*(R-L+1))%mod;
}
void pushdown(int id,int L,int R) {
	int mid=(L+R)/2;
	lazyb[id<<1] = (lazyb[id<<1]+lazyb[id]*lazya[id<<1])%mod , lazya[id<<1] = lazya[id<<1]*lazya[id]%mod;
	lazyb[id<<1|1] = (lazyb[id<<1|1]+lazyb[id]*lazya[id<<1|1])%mod , lazya[id<<1|1] = lazya[id<<1|1]*lazya[id]%mod;
	upd(id<<1,L,mid),upd(id<<1|1,mid+1,R),lazya[id]=1,lazyb[id]=0;
}
int xga(int l,int r,int L,int R,int id,int buff) {
	//printf("l=%d,r=%d,L=%d,R=%d,id=%d\n",l,r,L,R,id);
	int mid=(L+R)/2;
	if(L==l&&R==r) lazya[id] = lazya[id] * buff % mod , lazyb[id] = lazyb[id] * buff % mod;
	else if(r<=mid) pushdown(id,L,R),xga(l,r,L,mid,id<<1,buff);
	else if(l> mid) pushdown(id,L,R),xga(l,r,mid+1,R,id<<1|1,buff);
	else pushdown(id,L,R),xga(l,mid,L,mid,id<<1,buff),xga(mid+1,r,mid+1,R,id<<1|1,buff);
	upd(id,L,R);
}
int xgb(int l,int r,int L,int R,int id,int buff) {
	int mid = (L+R)/2;
	if(L==l&&R==r) lazyb[id] = (lazyb[id] + buff) % mod;
	else if(r<=mid) pushdown(id,L,R),xgb(l,r,L,mid,id<<1,buff);
	else if(l> mid) pushdown(id,L,R),xgb(l,r,mid+1,R,id<<1|1,buff);
	else pushdown(id,L,R),xgb(l,mid,L,mid,id<<1,buff),xgb(mid+1,r,mid+1,R,id<<1|1,buff);
	upd(id,L,R);
}
int query(int l,int r,int L,int R,int id) {
	int mid = (L+R)/2;
	if(L==l&&R==r) return sum[id];
	pushdown(id,L,R);
	if(r<=mid) return query(l,r,L,mid,id<<1);
	else if(l> mid) return query(l,r,mid+1,R,id<<1|1);
	else return (query(l,mid,L,mid,id<<1)+query(mid+1,r,mid+1,R,id<<1|1))%mod;
}
int n,m,xx,yy,buf,opt;
signed main() {
	scanf("%d%d",&n,&mod);
	for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
	build(1,n,1);
	scanf("%d",&m);
	while(m--) {
		scanf("%d%d%d",&opt,&xx,&yy);
		if(opt==1) scanf("%d",&buf),xga(xx,yy,1,n,1,buf);
		if(opt==2) scanf("%d",&buf),xgb(xx,yy,1,n,1,buf);
		if(opt==3) printf("%d\n",query(xx,yy,1,n,1));
//		if(opt-3) {
//			for(int i = 1; i <= n; i++) printf("%d ",query(i,i,1,n,1));
//			printf("\n");
//		}
	}
	return 0;
}