#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int L=10,N=100005;
int cnt[L],a[N],n,m,q,x,y,l,r,g[N],tot,fac[L][N*16],opt;
struct Tree{
	int l,r,num,flag[L];
}T[N*4];
int ksm(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=(ll)x*x%m)
		if (y&1)ans=(ll)ans*x%m;
	return ans;
}
void solve(int x){
	memset(cnt,0,sizeof cnt);
	for (int i=1;i<=tot;i++)
		while (x%g[i]==0)cnt[i]++,x/=g[i];
	cnt[0]=x;
}
int calc(int x){
	int s=T[x].num;
	for (int i=1;i<=tot;i++)s=(ll)s*fac[i][T[x].flag[i]]%m;
	return s;
}
void build(int x,int l,int r){
	T[x].l=l;T[x].r=r;T[x].flag[0]=1;
	if (l==r){
		solve(a[l]);
		T[x].num=cnt[0];
		for (int i=1;i<=tot;i++)T[x].flag[i]=cnt[i];
		return;
	}
	int mid=(l+r)/2;
	build(x*2,l,mid);
	build(x*2+1,mid+1,r);
	T[x].num=(calc(x*2)+calc(x*2+1))%m;
}
void add(int x,int y[]){
	T[x].num=(ll)T[x].num*y[0]%m;
	T[x].flag[0]=(ll)T[x].flag[0]*y[0]%m;
	for (int i=1;i<=tot;i++)T[x].flag[i]+=y[i];
}
void down(int x){
	add(x*2,T[x].flag);
	add(x*2+1,T[x].flag);
	T[x].flag[0]=1;
	for (int i=1;i<=tot;i++)T[x].flag[i]=0;
}
void insert1(int x,int l,int r){
	if (T[x].l>r||l>T[x].r)return;
	if (T[x].l>=l&&T[x].r<=r){
		add(x,cnt);
		return;
	}
	int t=calc(x);
	down(x);
	assert(t==(calc(x*2)+calc(x*2+1))%m);
	insert1(x*2,l,r);
	insert1(x*2+1,l,r);
	T[x].num=(calc(x*2)+calc(x*2+1))%m;
}
void insert2(int x,int y){
	if (T[x].l==T[x].r){
		T[x].num=(ll)T[x].num*cnt[0]%m;
		for (int i=1;i<=tot;i++)T[x].flag[i]-=cnt[i];
		return;
	}
	down(x);
	int mid=(T[x].l+T[x].r)/2;
	if (y<=mid)insert2(x*2,y);
	else insert2(x*2+1,y);
	T[x].num=(calc(x*2)+calc(x*2+1))%m;
}
int find(int x,int l,int r){
	if (T[x].l>r||l>T[x].r)return 0;
	if (T[x].l>=l&&T[x].r<=r)return calc(x);
	down(x);
	T[x].num=(calc(x*2)+calc(x*2+1))%m;
	return (find(x*2,l,r)+find(x*2+1,l,r))%m;
}
int main(){
	scanf("%d%d",&n,&m);
	int phi=m,t=m;
	for (int i=1;i<=n;i++)scanf("%d",&a[i]);
	for (int i=2;i*i<=t;i++)
		if (t%i==0){
			g[++tot]=i;
			while (t%i==0)t/=i;
			phi/=i;phi*=i-1;
		}
	if (t!=1)g[++tot]=t,phi/=t,phi*=t-1;
	scanf("%d",&q);
	for (int i=1;i<=tot;i++){
		fac[i][0]=1;
		for (int j=1;j<=16*(q+1);j++)fac[i][j]=(ll)fac[i][j-1]*g[i]%m;
	}
	build(1,1,n);
	while (q--){
		scanf("%d",&opt);
		if (opt==1){
			scanf("%d%d%d",&l,&r,&x);
			solve(x);
			insert1(1,l,r);
		}
		if (opt==2){
			scanf("%d%d",&x,&y);
			solve(y);cnt[0]=ksm(cnt[0],phi-1);
			insert2(1,x);
		}
		if (opt==3){
			scanf("%d%d",&l,&r);
			printf("%d\n",find(1,l,r));
		}
	}
}