#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int n,m,op,l,r,x,a[114514],cpy[114514],y;
int ksm(int a,int b,int p){//a^b mod p
	if(b==0)return 1;
	int ans=1;
	while(b){
		if(b&1)ans=ans*a%p;
		a=a*a%p;
		b>>=1;	
	}
	return ans;
}
signed 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>>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){
			for(int i=l;i<=r;i++){
				cpy[i]=a[i];
			}
			sort(a+l+1,a+r+1);
			cout<<a[l+x-1]<<"\n";
		}else{
			cin>>y;
			int ans=0;
			for(int i=l;i<=r;i++){
				ans+=ksm(a[i],x,y);
				ans%=y;
			}
			cout<<ans%y<<"\n";
		}
	}
	return 0;
}