#include<cstdio>
#include<cstring>
const int N=1e5+5;
typedef long long ll;
int k[N],b[12],p,t,f;
ll P(ll x,int y=f-1){ll z=1;for(;y;y>>=1,x=x*x%p)if(y&1)z=z*x%p;return z;}
struct node{
int a[12],c,d,s;
void clear(){memset(a,0,t+1<<2);c=d=1;}
void operator+=(node x){
for(int i=1;i<=t;++i)a[i]+=x.a[i];
c=(ll)c*x.c%p;d=(ll)d*x.d%p;s=(ll)s*x.d%p;
}
void operator-=(node x){
c=c*P(x.c)%p;s=c;
for(int i=1;i<=t;++i)a[i]-=x.a[i],s=s*P(b[i],a[i])%p;
d=s;
}
void operator^=(int x){
clear();s=d=x%p;
for(int i=1;i<=t;++i)
while(!(x%b[i])){
x/=b[i];
++a[i];
}
c=x%p;
}
}c[N<<2],d;
void down(int x){
c[x<<1]+=c[x];
c[x<<1|1]+=c[x];
c[x].clear();
}
void build(int x,int l,int r){
if(l==r){c[x]^=k[l];return;}
int m=l+r>>1;c[x].clear();
build(x<<1,l,m);build(x<<1|1,m+1,r);
c[x].s=(c[x<<1].s+c[x<<1|1].s)%p;
}
void mul(int x,int l,int r,int u,int v){
if(l==u&&r==v){c[x]+=d;return;}
int m=l+r>>1;down(x);
if(v<=m)mul(x<<1,l,m,u,v);
else if(u>m)mul(x<<1|1,m+1,r,u,v);
else mul(x<<1,l,m,u,m),mul(x<<1|1,m+1,r,m+1,v);
c[x].s=(c[x<<1].s+c[x<<1|1].s)%p;
}
void div(int x,int l,int r,int y){
if(l==r){c[x]-=d;return;}
int m=l+r>>1;down(x);
if(y<=m)div(x<<1,l,m,y);
else div(x<<1|1,m+1,r,y);
c[x].s=(c[x<<1].s+c[x<<1|1].s)%p;
}
int query(int x,int l,int r,int u,int v){
if(l==u&&r==v)return c[x].s;
int m=l+r>>1;down(x);
if(v<=m)return query(x<<1,l,m,u,v);
else if(u>m)return query(x<<1|1,m+1,r,u,v);
else return(query(x<<1,l,m,u,m)+query(x<<1|1,m+1,r,m+1,v))%p;
}
int main(){
int n,x,y,z,q;
scanf("%d%d",&n,&p);x=p;
for(int i=1;i<=n;++i)scanf("%d",&k[i]);
for(int i=2;i*i<=x;++i)
if(!(x%i)){
b[++t]=i;
while(!(x%i))x/=i;
}
if(x>1)b[++t]=x;
f=p;for(int i=1;i<=t;++i)f-=f/b[i];
build(1,1,n);
scanf("%d",&q);
while(q--){
scanf("%d",&x);
if(x==1){
scanf("%d%d%d",&x,&y,&z);
d^=z;mul(1,1,n,x,y);
}
else if(x==2){
scanf("%d%d",&x,&y);
d^=y;div(1,1,n,x);
}
else{
scanf("%d%d",&x,&y);
printf("%d\n",query(1,1,n,x,y));
}
}
return 0;
}