#include<bits/stdc++.h>
using namespace std;

#define ll long long 
#define maxn 100000

ll m,n;
ll num[maxn];
ll s[maxn];

ll qpow(ll a,ll b,ll p){
    ll ans=1;
    while(b){
        if(b&1){
            ans*=a;
            ans%=p;
        }
        a*=a;
        a%=p;
        b/=2;
    }
    return ans%p;
}


int main(){
    
    
    freopen("kdl.in","r",stdin);
    freopen("kdl.out","w",stdout);
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n>>m;
    
    for(int i=1;i<=n;i++){
        cin>>num[i];
    }
    
    while(m--){
        int op,l,r;
        ll x,y;
        cin>>op>>l>>r>>x;
        if(op==1){
            for(int i=l;i<=r;i++){
                num[i]+=x;
            }
        }
        else if(op==2){
            for(int i=l;i<=r;i++){
                num[i]=x;
            }
        }
        else if(op==3){
            for(int i=l,j=1;i<=r;i++,j++){
                s[j]=num[i];
            }
            sort(s+1,s+2+r-l);
            cout<<s[x]<<"\n";
        }
        else{
            cin>>y;
            ll u=0;
            for(int i=l;i<=r;i++){
                u+=qpow(num[i],x,y);
                u%=y;
            }
            cout<<u<<"\n";
        }
    
    }
    
    
    
    
    return 0;
}