[Code]

#include<bits/stdc++.h>
#define int long long
using namespace std;
unordered_map<int,int>Phi;
const int N=500100;
int a[N];
int phi(int x){
    if(Phi.count(x))return Phi[x];
    int now=x,qwq=x;
    for(int i=2;i*i<=x;++i)
        if(x%i==0){
            now=now/i*(i-1);
            while(x%i==0)x/=i;
        }
    if(x>1)now=now/x*(x-1);
    return Phi[qwq]=now;
}
inline int awa(int x,int ovo){
    return x<ovo?x:x%ovo+ovo;
}
int ksm(int a,int b,int c){
    int ans=1;
    while(b){
        if(b&1)
            ans=awa(ans*a,c);
        a=awa(a*a,c);
        b>>=1;
    }
    return ans;
}
struct Syx{
    int l,r,sum,YHB;
    void init(int p){
        l=r=p;
        sum=a[p],YHB=0;
    }
    void yhb(int x){
        YHB+=x,sum+=(r-l+1)*x;
    }
}z[N<<2];
Syx operator+(const Syx&l,const Syx&r){
    return {l.l,r.r,l.sum+r.sum,0ll};
}
void build(int l,int r,int rt){
    if(l==r)
        return z[rt].init(l);
    int mid=l+r>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    z[rt]=z[rt<<1]+z[rt<<1|1];
}
void pushyhb(int rt){
    if(z[rt].YHB){
        z[rt<<1].yhb(z[rt].YHB);
        z[rt<<1|1].yhb(z[rt].YHB);
        z[rt].YHB=0;
    }
}
void modify(int l,int r,int rt,int ll,int rr,int v){
    if(ll<=l&&r<=rr)
        return z[rt].yhb(v);
    int mid=l+r>>1;
    pushyhb(rt);
    if(ll<=mid)
        modify(l,mid,rt<<1,ll,rr,v);
    if(mid<rr)
        modify(mid+1,r,rt<<1|1,ll,rr,v);
    z[rt]=z[rt<<1]+z[rt<<1|1];
}
int query(int l,int r,int rt,int ll,int rr){
    if(ll<=l&&r<=rr)
        return z[rt].sum;
    int mid=l+r>>1,s=0;
    pushyhb(rt);
    if(ll<=mid)
        s+=query(l,mid,rt<<1,ll,rr);
    if(mid<rr)
        s+=query(mid+1,r,rt<<1|1,ll,rr);
    return s;
}
int n,m;
int calc(int l,int r,int p){
    if(p==1)return awa(query(1,n,1,l,l),p);
    if(l==r)return awa(query(1,n,1,l,l),p);
    return ksm(query(1,n,1,l,l),calc(l+1,r,phi(p)),p);
}
signed main() {
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    build(1,n,1);
    while(m--){
        int o;cin>>o;
        if(o==1){
            int l,r,v;
            cin>>l>>r>>v;
            modify(1,n,1,l,r,v);
        }else{
            int l,r,p;
            cin>>l>>r>>p;
            cout<<calc(l,r,p)<<'\n';
        }
    }
    return 0;
} // main