rt，我卡在第21个点了。
cf记录
可见第20个点跑了1.7s，所以可能是一些bug导致时间增长。

//g++ -g a.cpp -o a -std=c++14 -O0
#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
const int maxn=1e5+10,maxl=10;
int N,M,_M[12],mod,a[maxn];LL f[maxn<<3][12],fv[maxn<<3],phi;
int qd(){
	int rt=0;char c=getchar();
	while(c<'0'||c>'9')  c=getchar();
	while('0'<=c&&c<='9')  rt=(rt<<3)+(rt<<1)+c-48,c=getchar();
	return rt;
}
LL qsm(LL x,int y){
	LL rt=1;
	for(;y;y>>=1,x=x*x%mod)  if(y&1)  rt=rt*x%mod;
	return rt;
}
#define ni(x) (qsm(x,phi-1))
void facen(){
	int i=2,j=mod;phi=mod;
	for(;i*i<=j;i++){
		if(j%i==0)  _M[++_M[0]]=i,phi=phi/i*(i-1);
		while(j%i==0)  j/=i;
	}
	if(j>1)  _M[++_M[0]]=j,phi=phi/j*(j-1);
//	for(int i=1;i<=_M[0];i++)  printf("facen-> %d\n",_M[i]);
}
LL getv(int b){
//	if(!f[b][0])  return 0;//k
	LL k=f[b][0];
	for(int i=1;i<=_M[0];i++)  k=k*qsm(_M[i],f[b][i])%mod;
	return k;
}//in fact,nothing is 1,while 0 do mean sthother
void clear(int b){f[b][0]=1;for(int i=1;i<10;i++)  f[b][i]=0;}
void _upd(int b,int c){
//	printf("_upd %d<-%d:\n",b,c);
	for(int i=1;i<=_M[0];i++)  f[b][i]+=f[c][i];
	f[b][0]=f[b][0]*f[c][0]%mod;
//	for(int i=0;i<=_M[0];i++)  printf("%lld ",f[b][i]);
//	putchar('\n');
//	for(int i=0;i<=_M[0];i++)  printf("%lld ",f[c][i]);
//	putchar('\n');
//	printf("%lld\n",getv(b));
}
void upd1(int b,int x){
//	printf("upd %d %d:",b,x);
//	if(!x)  return;//k
	for(int i=1;i<=_M[0];i++){
		while(x&&x%_M[i]==0)  f[b][i]++,x/=_M[i];
	}
	f[b][0]=f[b][0]*x%mod;
//	for(int i=0;i<=_M[0];i++)  printf("%lld ",f[b][i]);
//	putchar('\n');
}
void upd2(int b,int x){
//	printf("upd %d %d:",b,x);
//	if(x==1)  return;//k
	for(int i=1;i<=_M[0];i++){
		while(x&&x%_M[i]==0)  f[b][i]--,x/=_M[i];
	}
	f[b][0]=f[b][0]*ni(x)%mod;
//	for(int i=0;i<=_M[0];i++)  printf("%lld ",f[b][i]);
//	putchar('\n');
}
void pushup(int t){fv[t]=(fv[t<<1]+fv[t<<1|1])%mod;}
void pushdown(int t,int l,int r){
	if(l==r)  return;
//	int m=(l+r)>>1;
//	printf("pd %d <%d,%d> -> %d<%d,%d> %d<%d,%d>\n",t,l,r,t<<1,l,m,t<<1|1,m+1,r);
//	printf("->%lld %lld\n",fv[t<<1],fv[t<<1|1]);
	fv[t<<1]=fv[t<<1]*getv(t)%mod;_upd(t<<1,t);
	fv[t<<1|1]=fv[t<<1|1]*getv(t)%mod;_upd(t<<1|1,t);
	clear(t);
//	printf("=%lld %lld\n",fv[t<<1],fv[t<<1|1]);
}
void build(int t,int l,int r){
//	printf("%d:<%d,%d>\n",t,l,r);
	clear(t);
	if(l==r){fv[t]=a[l]%mod;return upd1(t,a[l]);}
	int m=(l+r)>>1;
	build(t<<1,l,m),build(t<<1|1,m+1,r);
	pushup(t);
}
void change1(int t,int l,int r,int ul,int ur,int v){
//	printf("c1 %d %d,%d %d,%d %d\n",t,l,r,ul,ur,v);
	if(ul<=l&&r<=ur){fv[t]=fv[t]*v%mod;return upd1(t,v);}
	pushdown(t,l,r);int m=(l+r)>>1;
	if(ul<=m)  change1(t<<1,l,m,ul,ur,v);
	if(m<ur)  change1(t<<1|1,m+1,r,ul,ur,v);
	pushup(t);
}
void change2(int t,int l,int r,int p,int v){
	if(l==r){upd2(t,v);fv[t]=getv(t);return;}
	pushdown(t,l,r);int m=(l+r)>>1;
	if(p<=m)  change2(t<<1,l,m,p,v);
	else change2(t<<1|1,m+1,r,p,v);
	pushup(t);
}
LL ask(int t,int l,int r,int ul,int ur){
//	printf("ask %d <%d,%d>\n",t,l,r);
	if(ul<=l&&r<=ur)  return fv[t];
	pushdown(t,l,r);int m=(l+r)>>1;LL rt=0;
	if(ul<=m)  rt+=ask(t<<1,l,m,ul,ur);
	if(m<ur)  rt+=ask(t<<1|1,m+1,r,ul,ur);
	return rt%mod;
}
int main(){
//	freopen("in.txt","r",stdin);
	N=qd(),mod=qd();
	for(int i=1;i<=N;i++)  a[i]=qd();
	M=qd();facen();build(1,1,N);
	while(M--){
		int t=qd(),x=qd(),y=qd();
		if(t==1)  change1(1,1,N,x,y,qd());
		else if(t==2)  change2(1,1,N,x,y);
		else printf("%lld\n",ask(1,1,N,x,y));
	}
	return 0;
}