#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,a[100001],op,l,r,x,y;
ll fp(int xx,int yy,int mod){
    ll ans=1;
    while(yy>0){
        if(yy%2==1) ans=ans*xx%mod;
        yy/=2;
        xx=xx*xx%mod;
    }
    return ans%mod;
}
int main(){
	freopen("kdl.in","r",stdin);
	freopen("kdl.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	while(m--){
	    cin>>op>>l>>r>>x;
	    if(op==1) for(int i=l;i<=r;i++) a[i]+=x;
	    else if(op==2) for(int i=l;i<=r;i++) a[i]=x;
	    else if(op==3){
	        vector<int> b;
	        for(int i=l;i<=r;i++) b.push_back(a[i]);
	        sort(b.begin(),b.end());
	        cout<<b[x-1]<<endl;
        }else{
            cin>>y;
            ll fz=0;
            for(int i=l;i<=r;i++) fz=(fz+fp(a[i],x,y))%y;
            cout<<fz<<endl;
        }
    }
	return 0;
}