#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Rg register
#define RI Rg int
#define Cn const
#define CI Cn int&
#define I inline
#define W while
#define N 100000
using namespace std;
namespace FastIO
{
	#define FS 100000
	#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
	#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
	int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
	I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
	Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
	Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
	Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
int n,a[N+5],X,phi,pt,p[10];
I int QP(RI x,RI y=phi-1) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
struct INT
{
	int v,c[10];INT(){}INT(RI x){for(RI i=1;i<=pt;++i) for(c[i]=0;!(x%p[i]);x/=p[i],++c[i]);v=x;}
	I void S1() {v=1;for(RI i=1;i<=pt;++i) c[i]=0;}
	I void operator *= (Cn INT& o) {v=1LL*v*o.v%X;for(RI i=1;i<=pt;++i) c[i]+=o.c[i];}
	I void operator /= (Cn INT& o) {v=1LL*v*QP(o.v)%X;for(RI i=1;i<=pt;++i) c[i]-=o.c[i];}
	I int V() Cn {RI t=v;for(RI i=1;i<=pt;++i) t=1LL*t*QP(p[i],c[i])%X;return t;}
}Val;int val;
class SegmentTree
{
	private:
		#define PT RI l=1,RI r=n,RI o=1
		#define LT l,u,o<<1
		#define RT u+1,r,o<<1|1
		#define PU(o) (G[o]=(G[o<<1]+G[o<<1|1])%X)
		#define PD(o) (F[o]^1&&(T(o<<1,F[o],V[o]),T(o<<1|1,F[o],V[o]),V[o].S1(),F[o]=1))
		#define T(o,w,v) (G[o]=1LL*G[o]*w%X,F[o]=1LL*F[o]*w%X,V[o]*=v)
		int G[N<<2],F[N<<2];INT V[N<<2];
	public:
		void Bd(PT)
		{
			if(V[o].S1(),F[o]=1,l==r) return (void)(V[o]=INT(a[l]),G[o]=a[l]%X);RI u=l+r>>1;Bd(LT),Bd(RT),PU(o);
		}
		void M(CI L,CI R,PT)
		{
			if(L<=l&&r<=R) return (void)T(o,val,Val);RI u=l+r>>1;PD(o),L<=u&&(M(L,R,LT),0),R>u&&(M(L,R,RT),0),PU(o);
		}
		void D(CI x,CI v,PT)
		{
			if(l==r) return (void)(V[o]/=v,G[o]=V[o].V());RI u=l+r>>1;PD(o),x<=u?D(x,v,LT):D(x,v,RT),PU(o);
		}
		int Q(CI L,CI R,PT)
		{
			if(L<=l&&r<=R) return G[o];RI u=l+r>>1;PD(o);return ((L<=u?Q(L,R,LT):0)+(R>u?Q(L,R,RT):0))%X;
		}
}S;
int main()
{
	RI Qt,i,op,x,y;for(read(n,X),i=1;i<=n;++i) read(a[i]);
	for(x=X,phi=1,i=2;i*i<=x;++i) if(!(x%i)) {p[++pt]=i,phi*=i-1,x/=i;W(!(x%i)) phi*=i,x/=i;}x^1&&(p[++pt]=x,phi*=x-1);S.Bd();
	read(Qt);W(Qt--) read(op,x,y),op==1?(read(val),Val=val,S.M(x,y)):(op==2?S.D(x,y):writeln(S.Q(x,y)));return clear(),0;
}