#include <bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
using namespace std;
const int maxn=1e5+5;
typedef long long ll;

int k[maxn],b[11],smd,cnt,md;

int qpow(ll a,int b=smd-1){
	ll res=1;
	while(b){
		if (b&1) res=res*a%md;
		a=a*a%md;b>>=1;
	}
	return res;
}

struct node{
	int a[11],c,d,s;
	void clear(){
		memset(a,0,sizeof(a));
		c=d=1;
	} 
	void operator +=(node x){
		for (int i=1;i<=cnt;++i) a[i]+=x.a[i];
		c=1ll*c*x.c%md;d=1ll*d*x.d%md;s=1ll*s*x.d%md;
	}
	void operator -=(node x){
		c=1ll*c*qpow(x.c)%md;s=c;
		for (int i=1;i<=cnt;++i)
		a[i]-=x.a[i],s=1ll*s*qpow(b[i],a[i])%md;
		d=s;
	}
	void operator ^=(int x){
		clear();s=d=x%md;
		for (int i=1;i<=cnt;++i) while(!(x%b[i]))
		x/=b[i],++a[i];
		c=x%md;
	}
}t[maxn<<2],d;

void pushdown(int p){
	t[ls]+=t[p];
	t[rs]+=t[p];
	t[p].clear();
}

void build(int p,int l,int r){
	if (l==r) return t[p]^=k[l];
	t[p].clear();
	build(ls,l,mid),build(rs,mid+1,r);
	t[p].s=(t[ls].s+t[rs].s)%md;
}

void mul(int p,int l,int r,int L,int R){
	if (L<=l&&r<=R) return t[p]+=d;
	pushdown(p);
	if (mid>=R) mul(ls,l,mid,L,R);
	else if (mid<L) mul(rs,mid+1,r,L,R);
	else mul(ls,l,mid,L,R),mul(rs,mid+1,r,L,R);
	t[p].s=(t[ls].s+t[rs].s)%md;
}

void div(int p,int l,int r,int x){
	if (l==r) return t[p]-=d;
	pushdown(p);
	if (mid>=x) div(ls,l,mid,x);
	else div(rs,mid+1,r,x);
	t[p].s=(t[ls].s+t[rs].s)%md;
}

int query(int p,int l,int r,int L,int R){
	if (L<=l&&r<=R) return t[p].s;
	pushdown(p);
	if (mid>=R) return query(ls,l,mid,L,R);
	if (mid<L) return query(rs,mid+1,r,L,R);
	return (query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R))%md;
}

int main(){
	int n,q,x,y,z,op;
	scanf("%d%d",&n,&md);
	for (int i=1;i<=n;++i)
	scanf("%d",k+i);x=md;
	for (int i=2;i*i<=x;++i) if (!(x%i)){
		while(!(x%i)) x/=i;
		b[++cnt]=i;
	}
	if (x>1) b[++cnt]=x;
	smd=md;
	for (int i=1;i<=cnt;++i)
	smd=smd-smd/b[i];
	build(1,1,n);
	scanf("%d",&q);
	for (int i=1;i<=q;++i){
		scanf("%d",&op);
		if (op==1){
			scanf("%d%d%d",&x,&y,&z);
			d^=z;mul(1,1,n,x,y);
		}
		if (op==2){
			scanf("%d%d",&x,&y);
			d^=y;div(1,1,n,x);
		}
		if (op==3){
			scanf("%d%d",&x,&y);
			printf("%d\n",query(1,1,n,x,y));
		}
	}
	return 0;
}