// LUOGU_RID: 154250016
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
#define ull long long
using namespace std;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x>y?y:x;}
const int M=1e5+5,N=13;
int n,p,q,cnt,phi;
int a[M],prime[N];
inline ull quick(ull a,int n=phi-1)
{
	ull res=1;
	while(n)
	{
		if(n&1) res=res*a%p;
		n>>=1,a=a*a%p;
	}
	return res;
}
struct node {
	int a[N],c,d,s;
	inline void clear(){memset(a,0,sizeof(a)),c=d=1;}
	inline void operator +=(node x)
	{
		for(int i=1;i<=cnt;i++) a[i]+=x.a[i];
		c=(ull)c*x.c%p,d=(ull)d*x.d%p,s=(ull)s*x.d%p;
	}
	inline void operator -=(node x)
	{
		c=c*quick(x.c)%p;s=c;
		for(int i=1;i<=cnt;i++) a[i]-=x.a[i],s=s*quick(prime[i],a[i])%p;
		d=s;
	}
	inline void operator ^=(int x)
	{
		clear(),s=d=x%p;
		for(int i=1;i<=cnt;i++)
		{
			while(x%prime[i]==0) x/=prime[i],++a[i];
		}
		c=x%p;
	}
};node tree[M<<2],s;

inline void pushdown(int u)
{
	tree[u<<1]+=tree[u];
	tree[u<<1|1]+=tree[u];
	tree[u].clear();
}

inline void pushup(int u){tree[u].s=(tree[u<<1].s+tree[u<<1|1].s)%p;}

inline void build(int u,int ll,int rr)
{
	if(ll==rr)
	{
		tree[u]^=a[ll];
		return ;
	}
	int mid=(ll+rr)>>1;tree[u].clear();
	build(u<<1,ll,mid),build(u<<1|1,mid+1,rr);
	pushup(u);
}

inline void update1(int u,int ll,int rr,int L,int R)
{
	if(L<=ll&&rr<=R)
	{
		tree[u]+=s;
		return ;
	}
	int mid=(ll+rr)>>1;
	pushdown(u);
	if(mid>=L) update1(u<<1,ll,mid,L,R);
	if(R>mid) update1(u<<1|1,mid+1,rr,L,R);
	pushup(u);
}
inline void update2(int u,int ll,int rr,int x)
{
	if(ll==rr)
	{
		tree[u]-=s;
		return ;
	}
	int mid=(ll+rr)>>1;
	pushdown(u);
	if(mid>=x) update2(u<<1,ll,mid,x);
	else update2(u<<1|1,mid+1,rr,x);
	pushup(u);
}
/*
ull ans=0;
inline void query(int u,int ll,int rr,int L,int R)
{
	if(L<=ll&rr<=R)
	{
		ans+=tree[u].s;
		return ;
	}
	pushdown(u);
	int mid=(ll+rr)>>1;
	if(mid>=L) query(u<<1,ll,mid,L,R);
	if(R>mid) query(u<<1|1,mid+1,rr,L,R);
}*/
inline int query(int u,int ll,int rr,int L,int R)
{
	if(L==ll&&rr==R) return tree[u].s;
	int mid=(ll+rr)>>1;pushdown(u);
	if(R<=mid) return query(u<<1,ll,mid,L,R);
	else if(L>mid) return query(u<<1|1,mid+1,rr,L,R);
	else return (query(u<<1,ll,mid,L,mid)+query(u<<1|1,mid+1,rr,mid+1,R))%p;
}
signed main()
{
	cin>>n>>p;
	for(int i=1;i<=n;i++) cin>>a[i];
	int opt,l,r,x=p;phi=p;
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			prime[++cnt]=i;
			while(x%i==0) x/=i;
		}
	}
	if(x>1) prime[++cnt]=x;
	for(int i=1;i<=cnt;++i) phi-=phi/prime[i];
	build(1,1,n);
	cin>>q;
	while(q--)
	{
		cin>>opt;
		if(opt==1)
		{
			cin>>l>>r>>x;
			s^=x,update1(1,1,n,l,r);
		}
		else if(opt==2)
		{
			cin>>l>>x;
			s^=x,update2(1,1,n,l);
		}
		else
		{
			cin>>l>>r;
			//ans=0;query(1,1,n,l,r);
			//cout<<ans<<"\n";
			cout<<query(1,1,n,l,r)<<"\n";
		}
	}
	return 0;
}