#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+10;
struct cht{
	mutable int l,r,v;
	bool operator < (const cht &a)const{
		return l<a.l;
	} 
};
struct node{int c,v;}b[N];
bool cmp(node a,node b){return a.v<b.v;}
typedef set<cht>::iterator iter;
set<cht>tr;
iter it,L,R;
int n,m,cnt;
iter split(int p){
	if(p>n)return tr.end();
	it=tr.lower_bound(cht{p,0,0});
	if(it!=tr.end()&&it->l==p)return it;
	it--;int x=it->l,y=it->r,z=it->v;
	tr.erase(it),tr.insert(cht{x,p-1,z});
	return tr.insert(cht{p,y,z}).first;
}
void assign(int l,int r,int c){
	R=split(r+1),L=split(l);
	tr.erase(L,R);tr.insert(cht{l,r,c});
	return;
}
void add(int l,int r,int x){
	R=split(r+1),L=split(l);
	for(it=L;it!=R;it++){
		it->v=(it->v+x);
	}
	return;
}
int kth(int l,int r,int k){
	R=split(r+1),L=split(l);
	cnt=0;
	for(it=L;it!=R;it++)b[++cnt]=node{it->r-it->l+1,it->v};
	sort(b+1,b+1+cnt,cmp);
	for(int i=1;i<=cnt;i++){
		if(k<=b[i].c)return b[i].v;
		else k-=b[i].c;
	}
	return -1;
}
int ksm(int a,int b,int mod){
	int ans=1;a%=mod;
	while(b){
		if(b&1)ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
int ask(int l,int r,int x,int mod){
	int res=0,tmp;
	R=split(r+1),L=split(l);
	for(it=L;it!=R;it++){
		tmp=ksm(it->v,x,mod);
		res+=(it->r-it->l+1)*tmp%mod;
		res%=mod;
	}
	return res;
}
signed main(){
	freopen("kdl.in","r",stdin);
	freopen("kdl.out","w",stdout); 
	scanf("%lld %lld",&n,&m);
	for(int i=1,v;i<=n;i++){
		scanf("%lld",&v);
		tr.insert(cht{i,i,v});
	}
	int o,l,r,x,y;
	while(m--){
		scanf("%lld %lld %lld %lld",&o,&l,&r,&x);
		if(l>r)swap(l,r);
		if(o==4)scanf("%lld",&y);
		if(o==1)add(l,r,x);
		if(o==2)assign(l,r,x);
		if(o==3)printf("%lld\n",kth(l,r,x));
		if(o==4)printf("%lld\n",ask(l,r,x,y));
	}
	return 0;
}