#include<cstdio>
#include<cstring>
const int N=1e5+5;
typedef long long ll;
int k[N],b[12],p,t,f;
ll P(ll x,int y=f-1){ll z=1;for(;y;y>>=1,x=x*x%p) if(y&1) z=z*x%p;return z;}
struct node {
	int a[12],c,d,s;
	void clear(){memset(a,0,t+1<<2);c=d=1;}
	void operator +=(node x){
		for(int i=1;i<=t;++i) a[i]+=x.a[i];
		c=(ll)c*x.c%p;d=(ll)d*x.d%p;s=(ll)s*x.d%p;
	}
	void operator -=(node x){
		c=c*P(x.c)%p;s=c;
		for(int i=1;i<=t;++i) a[i]-=x.a[i],s=s*P(b[i],a[i])%p;
		d=s;
	}
	void operator ^=(int x){
		clear();s=d=x%p;
		for(int i=1;i<=t;++i)
			while(!(x%b[i])){
				x/=b[i];
				++a[i];
			}
		c=x%p;
	}
}c[N<<2],d;
void down(int x){
	c[x<<1]+=c[x];
	c[x<<1|1]+=c[x];
	c[x].clear();
}
void build(int x,int l,int r){
	if(l==r){c[x]^=k[l];return;}
	int m=l+r>>1;c[x].clear();
	build(x<<1,l,m);build(x<<1|1,m+1,r);
	c[x].s=(c[x<<1].s+c[x<<1|1].s)%p;
}
void mul(int x,int l,int r,int u,int v){
	if(l==u && r==v){c[x]+=d;return;}
	int m=l+r>>1;down(x);
	if(v<=m) mul(x<<1,l,m,u,v);
	else if(u>m) mul(x<<1|1,m+1,r,u,v);
	else mul(x<<1,l,m,u,m),mul(x<<1|1,m+1,r,m+1,v);
	c[x].s=(c[x<<1].s+c[x<<1|1].s)%p;
}
void div(int x,int l,int r,int y){
	if(l==r){c[x]-=d;return;}
	int m=l+r>>1;down(x);
	if(y<=m) div(x<<1,l,m,y);
	else div(x<<1|1,m+1,r,y);
	c[x].s=(c[x<<1].s+c[x<<1|1].s)%p;
}
int query(int x,int l,int r,int u,int v){
	if(l==u && r==v) return c[x].s;
	int m=l+r>>1;down(x);
	if(v<=m) return query(x<<1,l,m,u,v);
	else if(u>m) return query(x<<1|1,m+1,r,u,v);
	else return (query(x<<1,l,m,u,m)+query(x<<1|1,m+1,r,m+1,v))%p;
}
int main(){
	int n,x,y,z,q;
	scanf("%d%d",&n,&p);x=p;
	for(int i=1;i<=n;++i) scanf("%d",&k[i]);
	for(int i=2;i*i<=x;++i)
		if(!(x%i)){
			b[++t]=i;
			while(!(x%i)) x/=i;
		}
	if(x>1) b[++t]=x;
	f=p;for(int i=1;i<=t;++i) f-=f/b[i];
	build(1,1,n);
	scanf("%d",&q);
	while(q--){
		scanf("%d",&x);
		if(x==1){
			scanf("%d%d%d",&x,&y,&z);
			d^=z;mul(1,1,n,x,y);
		}
		else if(x==2){
			scanf("%d%d",&x,&y);
			d^=y;div(1,1,n,x);
		}
		else {
			scanf("%d%d",&x,&y);
			printf("%d\n",query(1,1,n,x,y));
		}
	}
	return 0;
}