rt

#include<bits/stdc++.h>
#define int long long
#define lson 2*k
#define rson 2*k+1
using namespace std;

const int N=1e5+15;

struct tree
{
	int lazy1[10];
	int lazy3,val;//维护基础的值 
	int lazy2;//维护除法对答案的影响 
}t[N*4+15];

int mod,pp,fac[N+10],cnt=0;
int th[N+10][20],add[N+10];
int a[N+10];
int n;

inline int read(){
   int x=0,f=1;
   char ch=getchar();
   while(ch < '0' || ch > '9'){
        if(ch=='-') f = -1;
        ch = getchar();
   }
   while(ch >='0' && ch <= '9'){
        x = (x<<3) + (x<<1) + ch - '0';
        ch = getchar();
   }
   return x*f;
}

inline int quick_pow(int a,int b)
{
	int ans=1,base=a;
	while(b)
	{
		if(b&1)
		{
			ans=ans*base%mod;
		} 
		b>>=1;
		base=base*base%mod;
	}
	return (ans%mod);
}

inline int calc(int m)
{
	int res=1;
	for(int i=1;i<=cnt;i++)
	{
		res=(res*quick_pow(fac[i],th[m][i]))%mod;
	} 
	return res;
}

inline int get_oler(int m)
{
	int oler=m;
	for(int i=2;i<=m/i;i++)
	{
		if(m%i==0)
		{
			oler=oler/i*(i-1);
			while(m%i==0)
			{
				m/=i;
			}
		}
	}
	if(m>1)
	{
		oler=oler/m*(m-1);
	}
	return oler;
}

inline void get(int m)
{
	int size=sqrt(m);
	for(int i=2;i<=size;i++)
	{
		if(m%i==0)
		{
			fac[++cnt]=i;
			while(m%i==0)
			{
				m/=i;
			}
		}
	}
	if(m!=1)
	{
		fac[++cnt]=m;
	}
}

inline void push_down(int k,int l,int r)
{
	if(l==r)
	{
		return;
	}
	
	t[lson].lazy3=t[lson].lazy3*t[k].lazy3%mod;
	t[rson].lazy3=t[rson].lazy3*t[k].lazy3%mod;
		
	t[lson].lazy2=t[lson].lazy2*t[k].lazy2%mod;
	t[rson].lazy2=t[rson].lazy2*t[k].lazy2%mod;
		
	t[lson].val=t[lson].val*t[k].lazy2%mod;
	t[rson].val=t[rson].val*t[k].lazy2%mod;
		
	t[k].lazy3=1;
	t[k].lazy2=1;
	
	for(int i=1;i<=cnt;i++)
	{
		t[lson].lazy1[i]+=t[k].lazy1[i];
		t[rson].lazy1[i]+=t[k].lazy1[i];
		t[k].lazy1[i]=0;
	}
	return;
}

inline void push_up(int k)
{
	t[k].val=(t[lson].val+t[rson].val)%mod;
}

inline void build(int k,int l,int r)
{
	t[k].lazy3=1;
	t[k].lazy2=1;
	//memset(t[k].lazy1,0,sizeof(t[k].lazy1));
	//t[k].lazy1[l]=0;
	if(l==r)
	{
		t[k].val=a[l]*calc(l)%mod;
		return;
	}
	int mid=(l+r)>>1;
	build(2*k,l,mid);
	build(2*k+1,mid+1,r);
	push_up(k);
}

inline void update1(int k,int l,int r,int ln,int rn,int x,int _x)
{
	if(ln<=l&&rn>=r)
	{
		t[k].val=t[k].val*x%mod;
		t[k].lazy3=t[k].lazy3*_x%mod;
		t[k].lazy2=t[k].lazy2*x%mod;
		for(int i=1;i<=cnt;i++)
		{
			t[k].lazy1[i]+=add[i];
		}
		return;
	}
	push_down(k,l,r);
	int mid=(l+r)>>1;
	if(ln<=mid)
	{
		update1(2*k,l,mid,ln,rn,x,_x);
	}
	if(rn>mid)
	{
		update1(2*k+1,mid+1,r,ln,rn,x,_x);
	}
	push_up(k);
}

inline void update2(int k,int l,int r,int ln,int rn,int x)
{
	//cout<<1;
	if(l>=ln&&r<=rn)
	{
		a[l]=a[l]*t[k].lazy3%mod;
		t[k].lazy3=1;
		for(int i=1;i<=cnt;i++) 
		{
			th[l][i]+=t[k].lazy1[i];
			t[k].lazy1[i]=0;
			while(x%fac[i]==0)
			{
				th[l][i]--;
				x/=fac[i];
			} 
		}
		a[l]=a[l]*quick_pow(x,pp-1)%mod;
		t[k].val=a[l]*calc(l)%mod;
		return;
	}
	push_down(k,l,r);
	int mid=(l+r)>>1;
	if(ln<=mid)
	{
		update2(2*k,l,mid,ln,rn,x);
	}
	else
	{
		update2(2*k+1,mid+1,r,ln,rn,x);
	}
	//cout<<1;
	push_up(k);
}

inline int query(int k,int l,int r,int ln,int rn)
{
	if(l>=ln&&r<=rn)
	{
		return t[k].val%mod;
	}
	push_down(k,l,r);
	//cout<<1<<endl;
	int ans=0;
	int mid=(l+r)>>1;
	if(ln<=mid)
	{
		ans+=query(2*k,l,mid,ln,rn);
		ans%=mod;
	}
	if(rn>mid)
	{
		ans+=query(2*k+1,mid+1,r,ln,rn);
		ans%=mod;
	}
	//cout<<1;
	return ans%mod;
}


signed main()
{
	//memset(lazy3,1,sizeof lazy3);
	//fill(lazy3,lazy3+N,1);
	//cout<<lazy3[1]<<" ";
	//memset(val,0,sizeof val);
//	ios::sync_with_stdio(false);
//	cin.tie(nullptr);
	n=read();
	mod=read();
	pp=get_oler(mod);
	get(mod);
	for(int i=1;i<=n;i++)
	{
		//cin>>a[i];
		a[i]=read();
		for(int j=1;j<=cnt;j++)
		{
			while(a[i]%fac[j]==0)
			{
				a[i]/=fac[j];
				th[i][j]++;
			}
		}
	}
	build(1,1,n);
//	for(int i=1;i<=n+10;i++)
//	{
//		cout<<val[i]<<" ";
//	}
//	cout<<endl;
	int m;
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int q;
		q=read();
		//cin>>q;
		if(q==1)
		{
			int l,r,x;
			l=read();
			r=read();
			x=read();
			//cin>>l>>r>>x;
			int _x=x;
			for(int j=1;j<=cnt;j++)
			{
				add[j]=0;
				if(_x%fac[j]==0)
				{
					add[j]++;
					_x/=fac[j];
				}
			}
			update1(1,1,n,l,r,x,_x);
//			for(int i=1;i<=n+10;i++)
//			{
//				cout<<val[i]<<" ";
//			}
//			cout<<endl;
		}
		if(q==2)
		{
			int point,x;
			point=read();
			x=read();
			//cin>>point>>x;
			update2(1,1,n,point,point,x);
		}
		if(q==3)
		{
			int l,r;
			l=read();
			r=read();
			//cin>>l>>r;
			//cout<<1<<endl;
			cout<<query(1,1,n,l,r)%mod<<endl;
		}
	}
	return 0;
}