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

#define ll long long
#define cpy(a,b) copy(begin(a),end(a),begin(b))
#define ld long double
#define dot(x) fixed<<setprecision(x)
#define foru(a,b,c) for(ll a=b;a<=c;a++)

ll n,m,a[100005],b[100005];

ll ksm(ll a,ll e,ll mod){
    a%=mod;
    if(a<0)a+=mod;
    ll r=1;
    while(e>0){
        if(e&1)r=(r*a)%mod;
        a=(a*a)%mod;
        e>>=1;
    }
    return r;
}

int main(){
    freopen("kdl.in" ,"r",stdin );
    freopen("kdl.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin>>n>>m;
    foru(i,1,n)cin>>a[i];
    foru(i,1,m){
        ll l,r,op,x,y;
        cin>>op;
        if(op==1){
            cin>>l>>r>>x;
            foru(j,l,r)a[j]+=x;
        }else if(op==2){
            cin>>l>>r>>x;
            foru(j,l,r)a[j]=x;
        }else if(op==3){
            cin>>l>>r>>x;
            foru(i,l,r)b[i]=a[i];
            sort(b+l,b+r+1);
            cout<<b[l+x-1]<<endl;
        }else{
            cin>>l>>r>>x>>y;
            ll ans=0;
            foru(i,l,r){
                ans+=ksm(a[i],x,y);
            }
            cout<<ans%y<<endl;
        }
    }
    return 0;
}