#include<bits/stdc++.h>
#define mid (l+r>>1)
#define ls l,mid,rt<<1
#define rs mid+1,r,rt<<1|1 
using namespace std;
const int N=4e5+10;
int n,mod,pri[11],laz[N],laz2[N],pnt=0,cal[N],tag[N][11],a[N],q;
int getphi(int t)
{
	int ret=t;
	for(int i=2;i*i<=t;i++) if(t%i==0){
		while(t%i==0) t=t/i;
		ret=ret/i*(i-1);
		pri[++pnt]=i;
    }
    if(t!=1) ret=ret/t*(t-1),pri[++pnt]=t;
    return ret;
}
void update(int rt){
	cal[rt]=(cal[rt<<1]+cal[rt<<1|1])%mod;
}
void build(int l,int r,int rt)
{
	laz[rt]=laz2[rt]=1;
	if(l==r) {
		int e=a[l];
		for(int i=1;i<=pnt;i++) while(e%pri[i]==0) e=e/pri[i],tag[rt][i]++;
		laz2[rt]=e;
		cal[rt]=a[l];
		return ;
	}
	build(ls);build(rs);
	update(rt); 
}
void add(int rt,int lz,int lz2,int *tg){
	cal[rt]=1ll*cal[rt]*lz%mod;
	laz[rt]=1ll*laz[rt]*lz%mod;
	laz2[rt]=1ll*laz2[rt]*lz2%mod;
	for(int i=1;i<=pnt;i++) tag[rt][i]+=tg[i];
}
void pushdown(int rt) {
	add(rt<<1,laz[rt],laz2[rt],tag[rt]);add(rt<<1|1,laz[rt],laz2[rt],tag[rt]);
	laz[rt]=1;laz2[rt]=1;memset(tag[rt],0,sizeof(tag[rt]));
}
#define limit al,ar,ad,ad2,Ad
void mul(int l,int r,int rt,int al,int ar,int ad,int ad2,int *Ad) {
	if(al<=l&&ar>=r) return add(rt,ad,ad2,Ad),void();
	pushdown(rt);
	if(mid>=al) mul(ls,limit);
	if(mid+1<=ar) mul(rs,limit);
	update(rt);
}
int ksm(int a,int b) {
	int tmp=1;
	while(b) {
		if(b&1) tmp=1ll*tmp*a%mod;
		a=1ll*a*a%mod; 
		b>>=1;
	}
	return tmp;
}
void div(int l,int r,int rt,int p,int ad,int *Ad) {
	if(l==r) {
		laz2[rt]=1ll*laz2[rt]*ad%mod;
		cal[rt]=laz2[rt];
		for(int i=1;i<=pnt;i++) tag[rt][i]-=Ad[i],cal[rt]=1ll*ksm(pri[i],tag[rt][i])*cal[rt]%mod;
		return ;
	}
	pushdown(rt);
	if(p<=mid) div(ls,p,ad,Ad);else div(rs,p,ad,Ad);
	update(rt);
}
int qurry(int l,int r,int rt,int al,int ar) {
	if(al<=l&&ar>=r) return cal[rt]%mod;
	int ans=0;
	pushdown(rt);
	if(mid>=al) ans+=qurry(ls,al,ar);
	if(mid+1<=ar) ans+=qurry(rs,al,ar);
	return ans%mod;
}
int main()
{
	scanf("%d%d",&n,&mod);
	const int tmp=getphi(mod)-1;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	build(1,n,1);
	scanf("%d",&q);
	int cnt[11];
	for(int i=1,o,a,b,c,cc;i<=q;i++) {
		scanf("%d%d%d",&o,&a,&b);
		if(o==1) {
			scanf("%d",&c);
			int cc=c;
			for(int i=1;i<=pnt;i++) {
				cnt[i]=0;
				while(cc%pri[i]==0) cc/=pri[i],cnt[i]++;
			}
			mul(1,n,1,a,b,c,cc,cnt);
		}
		else if(o==2) {
			for(int i=1;i<=pnt;i++) {
				cnt[i]=0;
				while(b%pri[i]==0) b/=pri[i],cnt[i]++; 
			}
			div(1,n,1,a,ksm(b,tmp),cnt);
		}
		else printf("%d\n",qurry(1,n,1,a,b));
	}
	return 0;
}