#include<bits/stdc++.h>
using namespace std;
int t[500010],n,m,op,l,r,x,p[20000000+10],P[20000000+10];
void add(int x,int v){while(x<=n){t[x]+=v;x+=(x&-x);}}
void upd(int l,int r,int v){add(l,v);add(r+1,-v);}
int get(int x){int r=0;while(x){r+=t[x];x-=(x&-x);}return r;}
bool f[20000000+10];
void sieve(){
    int cnt=0;P[1]=1;
    for(int i=2;i<=2e7;++i){
        if(!f[i]){p[cnt++]=i;P[i]=i-1;}
        for(int j=1;j<=cnt;++j){
            if(i*p[j]>2e7)break;
            f[i*p[j]]=1;
            if(!i%p[j]){P[i*p[j]]=P[i]*P[p[j]];break;}
            P[i*p[j]]=P[i]*(p[j]-1);
        }
    }
}
int p0w(int a,int b,int c){
    int r=1;a%=c;
    while(b){
        if(b&1)r=r*a%c;
        a=a*a%c;b>>=1;
    }
    return r;
} 
int que(int l,int r,int p){
    if(p==1)return 0;
    if(l==r)return get(l)%p;
    return p0w(get(l),que(l+1,r,p)%P[p]+P[p],p);
}
int main(){
    sieve();
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>l;
        upd(i,i,l);
    }
    while(m--){
        cin>>op>>l>>r>>x;
        if(op==1)upd(l,r,x);
        else cout<<que(l,r,x)<<"\n";
    }
    return 0;
}