rt

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define me(a,b) memset(a,b,sizeof a)
#define L(i,l,r) for(int i=l;i<=r;i++)
#define R(i,l,r) for(int i=r;i>=l;i--)
const int N=1e5+10;
int n,m,MOD,a[N];
struct Node{
	int l,r;
	int d;
	int time,add;
}tr[N<<2];
void pushup(int u){
	tr[u].d=(tr[ls(u)].d+tr[rs(u)].d)%MOD;
}
void build(int u,int l,int r){
	if(l==r){
		tr[u]={l,r,a[l],1,0};
		return;
	}
	tr[u]={l,r,0,1,0};
	int mid=l+r>>1;
	build(ls(u),l,mid);
	build(rs(u),mid+1,r);
	pushup(u);
}
void maketag(int u,int o,int opt){
	if(opt==1) tr[u].d=(tr[u].d*o)%MOD,tr[u].add=(tr[u].add*o)%MOD,tr[u].time=(tr[u].time*o)%MOD;
	if(opt==2) tr[u].d=(tr[u].d+o*(tr[u].r-tr[u].l+1))%MOD,tr[u].add=(tr[u].add+o)%MOD;
}
void pushdown(int u){
	if(tr[u].time!=1){ // 先传乘法，再传加法，因为乘法的 maketag 会对加法懒标记造成影响 
		maketag(ls(u),tr[u].time,1);
		maketag(rs(u),tr[u].time,1);
		tr[u].time=1;
	}
	if(tr[u].add){
		maketag(ls(u),tr[u].add,2);
		maketag(rs(u),tr[u].add,2);
		tr[u].add=0;
	}
}
void modify(int u,int l,int r,int o,int opt){
	if(tr[u].l>=l&&tr[u].r<=r){
		maketag(u,o,opt);
		return;
	}else{
		pushdown(u);
		int mid=tr[u].l+tr[u].r>>1;
		if(l<=mid) modify(ls(u),l,r,o,opt);
		if(r>mid) modify(rs(u),l,r,o,opt);
		pushup(u);
	}
}
int query(int u,int l,int r){
	if(tr[u].l>=l&&tr[u].r<=r){
		return tr[u].d;
	}else{
		pushdown(u);
		int ret=0;
		int mid=tr[u].l+tr[u].r>>1;
		if(l<=mid) ret+=query(ls(u),l,r);
		if(r>mid) ret+=query(rs(u),l,r);
		return ret;
	}
}
signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>MOD;
	L(i,1,n) cin>>a[i];
	build(1,1,n);
	cin>>m;
	while(m--){
		int opt,l,r,c;
		cin>>opt>>l>>r;
		if(opt<=2){
			cin>>c;
			modify(1,l,r,c,opt);
		}else cout<<query(1,l,r)<<'\n';
	}
	return 0;
}