#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
const int N=1e5+10;
int n,p,m,tot,phi,fac[13],tmp[13];
struct node{
	int sum,mul,res,fac[13];
}t[N<<2];
inline int read(){
	int x=0;char c=getchar();
	while(!isdigit(c))c=getchar();
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x;	
}
inline int getphi(int n){
	int ans=n;
	for(int i=2;i*i<=n;++i){
		if(n%i==0){
			ans=1ll*ans*(i-1)/i;
			while(n%i==0) n/=i;
		}
	}
	if(n>1) ans=1ll*ans*(n-1)/n;
	return ans;	
}
inline void div(int n){
	for(int i=2;i*i<=n;++i){
		if(n%i==0){
			fac[++tot]=i;
			while(n%i==0) n/=i;
		}
	}
	if(n>1) fac[++tot]=n;
}
inline int work(int w){
	for(int i=1;i<=tot;++i){
		tmp[i]=0;
		while(w%fac[i]==0) tmp[i]++,w/=fac[i];
	}
	return w%p;
}
inline int ksm(int a,int b=phi-1){
	int s=1;
	for(;b;b>>=1,a=1ll*a*a%p) if(b&1) s=1ll*s*a%p;
	return s;
}
inline void build(int k,int l,int r){
	t[k].mul=t[k].res=1;
	if(l==r){
		t[k].sum=read();
		t[k].res=work(t[k].sum),t[k].sum%=p;
		for(int i=1;i<=tot;++i) t[k].fac[i]=tmp[i];
		return;
	}
	build(k<<1,l,mid),build(k<<1|1,mid+1,r);
	t[k].sum=(t[k<<1].sum+t[k<<1|1].sum)%p;
}
inline void mul(int k,int w,int res,int *tmp){
	t[k].res=1ll*t[k].res*res%p;
	for(int i=1;i<=tot;++i) t[k].fac[i]+=tmp[i];
	t[k].mul=1ll*t[k].mul*w%p,t[k].sum=1ll*t[k].sum*w%p;
}
inline void Div(int k,int res){
	t[k].res=1ll*t[k].res*ksm(res)%p;
	int x=t[k].res;
	for(int i=1;i<=tot;++i){
		t[k].fac[i]-=tmp[i];
		x=1ll*x*ksm(fac[i],t[k].fac[i])%p;
	}
	t[k].sum=x;
}
inline void down(int k){
	if(t[k].mul!=1||t[k].res!=1){
		mul(k<<1,t[k].mul,t[k].res,t[k].fac),mul(k<<1|1,t[k].mul,t[k].res,t[k].fac);
		t[k].mul=t[k].res=1;
		for(int i=1;i<=tot;++i) t[k].fac[i]=0;
	}
}
inline void mul(int k,int l,int r,int x,int y,int w,int res){
	if(x>r||y<l) return;
	if(x<=l&&r<=y) return mul(k,w,res,tmp);
	down(k);
	mul(k<<1,l,mid,x,y,w,res);mul(k<<1|1,mid+1,r,x,y,w,res);
	t[k].sum=(t[k<<1].sum+t[k<<1|1].sum)%p;
}
inline void div(int k,int l,int r,int x,int w){
	if(l==r) return Div(k,w);
	down(k);
	x<=mid?div(k<<1,l,mid,x,w):div(k<<1|1,mid+1,r,x,w);
	t[k].sum=(t[k<<1].sum+t[k<<1|1].sum)%p;
}
inline int que(int k,int l,int r,int x,int y){
	if(x>r||y<l) return 0;
	if(x<=l&&r<=y) return t[k].sum;
	down(k);
	return (que(k<<1,l,mid,x,y)+que(k<<1|1,mid+1,r,x,y))%p;
}
int main(){
	n=read(),p=read(),phi=getphi(p),div(p);
	build(1,1,n),m=read();
	while(m--){
		int op=read(),x=read(),y=read(),w;
		if(op==1) w=read(),mul(1,1,n,x,y,w,work(w));
		else if(op==2) div(1,1,n,x,work(y));
		else printf("%d\n",que(1,1,n,x,y));
	}		
	return 0;
}