#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7;
struct node{
	int l,r;
	mutable int val;
	node(int l,int r,int val) :l(l),r(r),val(val){};
	bool operator<(const  node &a)const{
		return l<a.l;
	} 
};
set<node>odt;
int n,m;
int qpow(int n,int k,int p){
	int ans=1;
    while(k){
        if(k&1){
            ans=ans*n%p;
        }
        n=n*n%p;
        k>>=1;
    }
    return ans;
}
auto split(int x){
	auto it=odt.lower_bound(node(x,-1,0));
	if(it!=odt.end()&&it->l==x){
		return it;
	}
	it--;
	int l=it->l,r=it->r,val=it->val;
	odt.erase(it);
	odt.insert(node(l,x-1,val));
	return odt.insert(node(x,r,val)).first; 
}
void assgin(int l,int r,int v){
	auto end=split(r+1),begin=split(l);
	odt.erase(begin,end);
	odt.insert(node(l,r,v));
}
void add(int l,int r,int v){
	auto end=split(r+1),begin=split(l);
	for(auto it=begin;it!=end;it++){
		it->val+=v;
	}
}
int ask_pow(int l,int r,int x,int p){
	auto end=split(r+1),begin=split(l);
	int ans=0;
	for(auto it=begin;it!=end;it++){
		int aa=it->val,ll=it->l,rr=it->r;
		ans=(ans+qpow(aa,x,p)*(rr-ll+1)%p)%p;
	}
	return ans;
}
int ask_k_th(int l,int r,int x){
	auto end=split(r+1),begin=split(l);
	vector<pair<int,int> >g;
	for(auto it=begin;it!=end;it++){
		int ll=it->l,rr=it->r;
		g.push_back(make_pair(it->val,rr-ll+1));
	}
	sort(g.begin(),g.end());
	for(int i=0;i<g.size();i++){
		x-=g[i].second;
		if(x<=0){
			return g[i].first;
		}
	}
}
signed main(){
	freopen("kdl.in","r",stdin);
	freopen("kdl.out","w",stdout); 
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int v;
		cin>>v;
		odt.insert(node(i,i,v));
	}
	for(int i=1;i<=m;i++){
		int op,l,r,x,y;
		cin>>op>>l>>r>>x;
		if(l>r){
			swap(l,r);
		}
		if(op==1){
			add(l,r,x);
		}
		else if(op==2){
			assgin(l,r,x);
		}
		else if(op==3){
			cout<<ask_k_th(l,r,x)<<"\n";
		}
		else if(op==4){
			cin>>y;
			cout<<ask_pow(l,r,x,y)<<"\n";
		}
	}
	
	return 0;
}