#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int N=1e5+10;
int n,mod,q,fac[30],phi,len,tmp[30],a[N];
struct Segment_Tree{
	int dat,f[24],mul,fmul,l,r;
	#define ls(p) (p<<1)
	#define rs(p) (p<<1|1)
}t[N<<2];
inline int work(int x){
	for(int i=1;i<=len;i++){
		tmp[i]=0;
		while(x%fac[i]==0)tmp[i]++,x/=fac[i];
	}
	return x%mod;
}
inline void up(int p){t[p].dat=(t[ls(p)].dat+t[rs(p)].dat)%mod;}
inline void mul(int p,int x,int fmul,int *ff){
	t[p].fmul=t[p].fmul*fmul%mod;
	for(int i=1;i<=len;i++) t[p].f[i]+=ff[i];
	t[p].mul=t[p].mul*x%mod,t[p].dat=t[p].dat*x%mod;
}
inline int qpow(int x,int y){
	int sum=1;
	for(;y;y>>=1,x=x*x%mod)if(y&1)sum=sum*x%mod;
	return sum;
}
inline void divv(int p,int fmul){
	t[p].fmul=t[p].fmul*qpow(fmul,phi-1)%mod;
	int x=t[p].fmul;
	for(int i=1;i<=len;i++) t[p].f[i]-=tmp[i],
	x=x*qpow(fac[i],t[p].f[i])%mod;
	t[p].dat=x;
}
inline void down(int p){
	if(t[p].mul!=1||t[p].fmul!=1){
		mul(ls(p),t[p].mul,t[p].fmul,t[p].f);
		mul(rs(p),t[p].mul,t[p].fmul,t[p].f);
		t[p].fmul=t[p].mul=1;
		for(int i=1;i<=len;i++) t[p].f[i]=0;	
	}
}
inline void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r){
		t[p].dat=a[l]%mod;
		t[p].fmul=work(a[l]);
		for(int i=1;i<=len;i++) t[p].f[i]=tmp[i];
		return ;
	}
	t[p].mul=t[p].fmul=1;
	int mid=(l+r)>>1;
	build(ls(p),l,mid);build(rs(p),mid+1,r);
	up(p);
}
inline int ph(int x){
	int res=x;
	for(int i=2;i*i<=x;i++){
		if(x%i!=0)continue;
		res=res*(i-1)/i;
		while(x%i==0)x/=i;
	}
	if(x>1)res=res*(x-1)/x;
	return res;
}
inline void d(int x){
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			fac[++len]=i;
			while(x%i==0)x/=i;
		}
	}
	if(x>1)fac[++len]=x;
}
inline void modimul(int p,int l,int r,int x,int fmul){
	if(l<=t[p].l&&t[p].r<=r)return mul(p,x,fmul,tmp);
	down(p);int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)modimul(ls(p),l,r,x,fmul);
	if(r>mid)modimul(rs(p),l,r,x,fmul);
	up(p);
}
inline void modidiv(int p,int x,int fmul){
	if(t[p].l==t[p].r&&t[p].r==x)return divv(p,fmul);
	int mid=(t[p].l+t[p].r)>>1;down(p);
	if(x<=mid)modidiv(ls(p),x,fmul);
	else modidiv(rs(p),x,fmul);
	up(p);
}
inline int query(int p,int l,int r){
	if(l<=t[p].l&&t[p].r<=r)return t[p].dat%mod;
	int mid=(t[p].l+t[p].r)>>1,ans=0;down(p);
	if(l<=mid)ans+=query(ls(p),l,r);
	if(r>mid)ans=(query(rs(p),l,r)+ans)%mod;
	return ans%mod;
}
signed main(){
	n=read(),mod=read();phi=ph(mod);d(mod);
	for(int i=1;i<=n;i++)a[i]=read();
	build(1,1,n);q=read();
	int opt,l,r,x;
	while(q--){
		opt=read(),l=read(),r=read();
		if(opt==1)x=read(),modimul(1,l,r,x,work(x));
		else if(opt==2)modidiv(1,l,work(r));
		else cout<<query(1,l,r)<<endl;
	}
}