#include<bits/stdc++.h>
#define N 100005
#define ll long long 
using namespace std;
int n,m,mod;
int p[15],cnt;
struct node{
	int a[15];
	ll x;
	node(){
		memset(a,0,sizeof(a));
		x=1;
	}
	void clear(){
		for(int i=1;i<=cnt;i++) a[i]=0;
		x=1;
	}
}tag[N<<2];
ll ksm(ll x,int b){
	ll res=1;
	while(b){
		if(b&1) res=(res*x)%mod;
		x=(x*x)%mod;
		b>>=1;
	}
	return res;
}
void exgcd(int a,int b,int &x,int &y){
	if(!b){
		x=1,y=0;
		return ;
	}
	exgcd(b,a%b,x,y);
	int z=x;
	x=y;
	y=z-(a/b)*y;
}
int inv(int a,int b){
	int x,y;
	exgcd(a,b,x,y);
	return ((ll)x+b)%b;
}
node operator *(const node &a,const node &b){
	node res;
	for(int i=1;i<=cnt;i++) res.a[i]=a.a[i]+b.a[i];
	res.x=(a.x*b.x)%mod;
	return res;
}
node operator /(const node &a,const node &b){
	node res;
	for(int i=1;i<=cnt;i++) res.a[i]=(a.a[i]-b.a[i]);
	res.x=(a.x*inv(b.x,mod))%mod;
	return res;
}
ll calc(node x){
	ll res=x.x;
	for(int i=1;i<=cnt;i++) res=(res*ksm(p[i],x.a[i])%mod);
	return res;
}
node divide(int x){
	node res;
	for(int i=1;i<=cnt;i++)
		while(x%p[i]==0) x/=p[i],res.a[i]++;
	res.x=x;
	return res;
}
int a[N];
ll sum[N<<2],mul[N<<2];
void push_up(int u){
	sum[u]=(sum[u<<1]+sum[u<<1|1])%mod;
}
void push_tag(int u,int x,node v){
	tag[u]=tag[u]*v;
	mul[u]=(mul[u]*x)%mod;
	sum[u]=(sum[u]*x)%mod;
}
void push_down(int u){
	if(mul[u]!=1){
		push_tag(u<<1,mul[u],tag[u]);
		push_tag(u<<1|1,mul[u],tag[u]);
		tag[u].clear();
		mul[u]=1;
	}
}
void modify(int p,int l,int r,int ql,int qr,int x,node v){
	if(ql<=l&&qr>=r){
		push_tag(p,x,v);
		return ;
	}
	push_down(p);
	int mid=(l+r)>>1;
	if(ql<=mid) modify(p<<1,l,mid,ql,qr,x,v);
	if(qr>mid) modify(p<<1|1,mid+1,r,ql,qr,x,v);
	push_up(p);
}
void Modify(int p,int l,int r,int x,node v){
	if(l==r){
		tag[p]=tag[p]/v;
 		sum[p]=calc(tag[p]);
		return ;
	}
	push_down(p);
	int mid=(l+r)>>1;	
	if(x<=mid) Modify(p<<1,l,mid,x,v);
	else Modify(p<<1|1,mid+1,r,x,v);
	push_up(p);	
}
ll query(int p,int l,int r,int ql,int qr){
	if(ql<=l&&qr>=r) return sum[p];
	ll res=0;
	int mid=(l+r)>>1;
	push_down(p);
	if(ql<=mid) res=(res+query(p<<1,l,mid,ql,qr))%mod;
	if(qr>mid) res=(res+query(p<<1|1,mid+1,r,ql,qr))%mod;
	return res;
}
void build(int p,int l,int r){
	mul[p]=1;
	if(l==r){
		sum[p]=a[l]%mod;
		tag[p]=divide(a[l]);
		return ;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	push_up(p);
}
int main(){
	scanf("%d%d",&n,&mod);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	int x=mod;
	for(int i=2;(ll)i*i<=mod;i++){
		if(x%i) continue;
		p[++cnt]=i;
		while(x%i==0) x/=i;
	}
	if(x>1) p[++cnt]=x;
	build(1,1,n);
	scanf("%d",&m);
	while(m--){
		int op,l,r,x;
		scanf("%d",&op);
		if(op==1){
			scanf("%d%d%d",&l,&r,&x);
			modify(1,1,n,l,r,x,divide(x));
		}
		if(op==2){
			scanf("%d%d",&l,&x);
			Modify(1,1,n,l,divide(x));
		}
		if(op==3){
			scanf("%d%d",&l,&r);
			printf("%lld\n",query(1,1,n,l,r));
		}
	}
	return 0;
}