#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,q,phi,mod;
int kp(int a,int b)
{
	int c=1;
	while(b)
	{
		if(b&1) c=1ll*c*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return c;
}
struct arr
{
	int x,y;
}b[100];
struct stp
{
	int val,p,a[10];
	void clear()
	{
		val=p=0;
		for(int i=1;i<=m;i++) a[i]=0;
	}
	void in(int x)
	{
		val=x%mod;
		for(int i=1;i<=m;i++)
			while(x%b[i].x==0) x/=b[i].x,++a[i];
		p=x;
	}
	void operator*(stp x)
	{
		p=p*x.p%mod;
		for(int i=1;i<=m;i++) a[i]+=x.a[i];
		val=val*x.val%mod;
	}
	void operator/(stp x)
	{
		p*=kp(x.p,phi-1);
		p%=mod;
		for(int i=1;i<=m;i++) a[i]-=x.a[i];
		val=p;
		for(int i=1;i<=m;i++) val=val*kp(b[i].x,a[i])%mod;
	}
}k,p;
struct segment_tree
{
	stp a[800005],lazy[800005];
	void pushdown(int k)
	{
		p=lazy[k];
		lazy[k<<1]*p;
		lazy[(k<<1)|1]*p;
		a[k<<1]*p;
		a[(k<<1)|1]*p;
		lazy[k].clear();
		lazy[k].val=lazy[k].p=1;
	}
	void build(int l,int r,int k,int x,stp y)
	{
		lazy[k].val=lazy[k].p=1;
		if(l==r)
		{
			a[k]=y;
			return;
		}
		int mid=(l+r)>>1;
		if(x<=mid) build(l,mid,k<<1,x,y);
		if(x>mid) build(mid+1,r,(k<<1)|1,x,y);
		a[k].val=a[k<<1].val+a[(k<<1)|1].val;
		a[k].val%=mod;
	}
	void update(int l,int r,int k,int x,int y,stp z)
	{
		if(l>=x&&r<=y)
		{
			a[k]*z;
			lazy[k]*z;
			return;
		}
		pushdown(k);
		int mid=(l+r)>>1;
		if(x<=mid) update(l,mid,k<<1,x,y,z);
		if(y>mid) update(mid+1,r,(k<<1)|1,x,y,z);
		a[k].val=a[k<<1].val+a[(k<<1)|1].val;
		a[k].val%=mod;
	}
	void div(int l,int r,int k,int x,stp y)
	{
		if(l==r)
		{
			a[k]/y;
			return;
		}
		pushdown(k);
		int mid=(l+r)>>1;
		if(x<=mid) div(l,mid,k<<1,x,y);
		if(x>mid) div(mid+1,r,(k<<1)|1,x,y);
		a[k].val=a[k<<1].val+a[(k<<1)|1].val;
		a[k].val%=mod;
	}
	int find(int l,int r,int k,int x,int y)
	{
		if(l>=x&&r<=y) return a[k].val;
		pushdown(k);
		int mid=(l+r)>>1,ans=0;
		if(x<=mid) ans=find(l,mid,k<<1,x,y);
		if(y>mid) ans+=find(mid+1,r,(k<<1)|1,x,y);
		return ans%mod;
	}
}st;
signed main()
{
	scanf("%lld%lld",&n,&mod);
	int p=mod;
	phi=mod;
	for(int i=2;i*i<=p;i++)
		if(p%i==0)
		{
			b[++m]={i,0};
			phi/=i;
			phi*=i-1;
			while(p%i==0) p/=i,++b[m].y;
		}
	if(p-1) b[++m]={p,1},phi/=p,phi*=p-1;
	for(int i=1;i<=n;i++)
	{
		int x;
		k.clear();
		scanf("%lld",&x);
		k.in(x);
		st.build(1,n,1,i,k);
	}
	scanf("%lld",&q);
	for(int i=1;i<=q;i++)
	{
		int bo,x,y,z;
		scanf("%lld%lld%lld",&bo,&x,&y);
		if(bo==1)
		{
			scanf("%lld",&z);
			k.clear();
			k.in(z);
			st.update(1,n,1,x,y,k);
		}
		if(bo==2)
		{
			k.clear();
			k.in(y);
			st.div(1,n,1,x,k);
		}
		if(bo==3) printf("%lld\n",st.find(1,n,1,x,y));
	}
	return 0;
}