#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
#define ls(x) x<<1
#define rs(x) x<<1
#define pushup(u) w[u]=w[ls(u)]+w[rs(u)]
#define ll long long
int n,mod,m; 
int a[N],siz[N<<2];
int op,t,g,c;
ll w[N<<2],add[N<<2],mul[N<<2];
void build(int u,int l,int r){
	siz[u]=r-l+1;
	mul[u]=1;
	if(l==r){
		w[u]=a[l];
		return;
	}
	int mid=l+r>>1;
	build(ls(u),l,mid);
	build(rs(u),mid+1,r);
	pushup(u);
}
void pushdown(int u){
	if(mul[u]!=1){
		w[ls(u)]*=mul[u]; 
		add[ls(u)]*=mul[u];
		mul[ls(u)]*=mul[u];
		w[ls(u)]%=mod;
		add[ls(u)]%=mod;
		mul[ls(u)]%=mod;
		w[rs(u)]*=mul[u]; 
		add[rs(u)]*=mul[u];
		mul[rs(u)]*=mul[u];
		w[rs(u)]%=mod;
		add[rs(u)]%=mod;
		mul[rs(u)]%=mod;
		mul[u]=1;
	}
	if(add[u]){
		w[ls(u)]+=add[u]*siz[ls(u)];
		add[ls(u)]+=add[u];
		w[ls(u)]%=mod;
		add[ls(u)]%=mod;
		w[rs(u)]+=add[u]*siz[rs(u)];
		add[rs(u)]+=add[u];
		w[rs(u)]%=mod;
		add[rs(u)]%=mod;
		add[u]=0;
	}
}
void modify_add(int u,int l,int r,int L,int R,int p){
	if(L<=l&&r<=R){
		w[u]+=p*siz[u];
		add[u]+=p;
		w[u]%=mod; add[u]%=mod;
	}
	else if(!(r<L||R<l)){
		pushdown(u);
		int mid=l+r>>1;
		modify_add(ls(u),l,mid,L,R,p);
		modify_add(rs(u),mid+1,r,L,R,p);
		pushup(u); 
	}
}
void modify_mul(int u,int l,int r,int L,int R,int p){
	if(L<=l&&r<=R){
		w[u]*=p;
		add[u]*=p; mul[u]*=p;
		w[u]%=mod;
		add[u]%=mod; mul[u]%=mod;
	}
	else if(!(r<L||R<l)){
		pushdown(u);
		int mid=l+r>>1;
		modify_mul(ls(u),l,mid,L,R,p);
		modify_mul(rs(u),mid+1,r,L,R,p);
		pushup(u); 
	}
}
ll qry(int u,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return w[u];
	}
	else if(!(r<L||R<l)){
		pushdown(u);
		int mid=l+r>>1;
		return (qry(ls(u),l,mid,L,R)%mod+qry(rs(u),mid+1,r,L,R)%mod)%mod;
	}
return 0;
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>mod;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
//	for(int i=1;i<=n;i++){
//		cout<<qry(1,1,n,i,i)<<" ";
//	}
//	cout<<"\n";
	cin>>m;
	while(m--){
		cin>>op>>t>>g;
		if(op==1){
			cin>>c;
			modify_mul(1,1,n,t,g,c);
		}
		else if(op==2){
			cin>>c;
			modify_add(1,1,n,t,g,c);
		}
		else{
			cout<<qry(1,1,n,t,g)<<"\n";	
		}
	}
return 0;
}