玄关求条

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define lson (k<<1)
#define rson (k<<1|1)
#define mid ((l+r)>>1)
const int N=1e5+10;

int n,mod,q;

int prime[11],cnt,ph;
 
int ksm(int base,int k){
	int res=1; base%=mod;
	while(k){
		if(k&1) res=res*base%mod;
		base=base*base%mod;
		k>>=1;
	}
	return res;
}

struct node{
	int x,num[11];
	node(){
	}
	node(int n){
		x=0,memset(num,0,sizeof(num));
		if(n==1){
			x=1; return ;
		}
		for(int i=1;i<=cnt;i++){
			int p=prime[i];
			while(n%p==0){
				num[i]++;
				n/=p;
			}
		}
		x=n;
	}
	int calc(){
		int ans=x;
		for(int i=1;i<=cnt;i++){
			int p=prime[i];
			ans=ans*ksm(p,num[i])%mod;
		}
		return ans;
	} 
}a[N];

void get_prime(){
	int tmp=mod;
	ph=mod;
	for(int i=2;i<=tmp/i;i++){
		if(tmp%i==0){
			cnt++; prime[cnt]=i;
			ph=ph/i*(i-1);
			while(tmp%i==0) tmp/=i;
		}
	}
	if(tmp>1){
		cnt++; prime[cnt]=tmp;
		ph=ph/tmp*(tmp-1);
	}
}

struct node_tr{
	int x,tag1;
	node tag2;
}tr[N<<2];

void pushup(int k){
	tr[k].x=(tr[lson].x+tr[rson].x)%mod;
}

void pushdown(int k){
	tr[lson].x=tr[lson].x*tr[k].tag1%mod;
	tr[lson].tag1=tr[lson].tag1*tr[k].tag1%mod;
	tr[lson].tag2.x=tr[lson].tag2.x*tr[k].tag2.x%mod;
	tr[rson].x=tr[rson].x*tr[k].tag1%mod;
	tr[rson].tag1=tr[rson].tag1*tr[k].tag1%mod;
	tr[rson].tag2.x=tr[rson].tag2.x*tr[k].tag2.x%mod;
	for(int i=1;i<=cnt;i++){
		tr[lson].tag2.num[i]+=tr[k].tag2.num[i];
		tr[rson].tag2.num[i]+=tr[k].tag2.num[i];
		tr[k].tag2.num[i]=0;
	}
	tr[k].tag1=tr[k].tag2.x=1;
}

void build(int k,int l,int r){
	tr[k].tag1=1;
	tr[k].tag2=node(1);
	if(l==r){
		tr[k].x=a[l].calc();
		return ;
	}
	build(lson,l,mid);
	build(rson,mid+1,r);
	pushup(k); 
}

void mdf(int k,int l,int r,int ql,int qr,int x,node xx){
	if(ql<=l&&r<=qr){
		tr[k].x=tr[k].x*x%mod;
		tr[k].tag1=tr[k].tag1*x%mod;
		tr[k].tag2=tr[k].tag2.x*xx.x%mod;
		for(int i=1;i<=cnt;i++) tr[k].tag2.num[i]+=xx.num[i];
		return ;
	}
	pushdown(k);
	if(ql<=mid) mdf(lson,l,mid,ql,qr,x,xx);
	if(qr>mid) mdf(rson,mid+1,r,ql,qr,x,xx);
	pushup(k);
}

void mdf(int k,int l,int r,int pos,int x){
	if(l==r){
		a[pos].x=a[pos].x*tr[k].tag2.x%mod;
		tr[k].tag2.x=1;
		for(int i=1;i<=cnt;i++){
			int p=prime[i];
			a[pos].num[i]+=tr[k].tag2.num[i];
			while(x%p==0) a[pos].num[i]--,x/=p;
			tr[k].tag2.num[i]=0;
		}
		a[pos].x=a[pos].x*ksm(x,ph-1)%mod;
		tr[k].x=a[pos].calc();
		return ;
	}
	pushdown(k); 
	if(pos<=mid) mdf(lson,l,mid,pos,x);
	else mdf(rson,mid+1,r,pos,x);
	pushup(k);
}

int qry(int k,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr){
		return tr[k].x;
	}
	pushdown(k);
	int ans=0;
	if(ql<=mid) ans=(ans+qry(lson,l,mid,ql,qr))%mod;
	if(qr>mid) ans=(ans+qry(rson,mid+1,r,ql,qr))%mod;
	return ans;
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>mod;
	get_prime();
	for(int i=1,x;i<=n;i++){
		cin>>x;
		a[i]=node(x);
	}
	build(1,1,n);
	cin>>q;
	int op,l,r,x;
	while(q--){
		cin>>op;
		if(op==1){
			cin>>l>>r>>x;
			mdf(1,1,n,l,r,x,node(x));
		}
		else if(op==2){
			cin>>l>>x;
			mdf(1,1,n,l,x);
		}
		else{
			cin>>l>>r;
			cout<<qry(1,1,n,l,r)<<'\n';
		}
	}
	return 0; 
}