/*#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,m,ans,a[N];
struct node{
	int l,r,v;
}t[2*N];
struct hs{
	int v,s;
};
vector<hs>q;
void pushdown(int p){
	if(t[p].v){
		t[p<<1].v=t[p<<1|1].v=t[p].v;
		t[p].v=0;
	}
}
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r){
		t[p].v=a[l];
		return;
	}
	int mid=((l+r)>>1);
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	return;
}
void increase(int p,int l,int r,int x){
	if(r<t[p].l||t[p].r<l) return;
	if(l<=t[p].l&&t[p].r<=r&&t[p].v){
		t[p].v+=x;
		return;
	}
	pushdown(p);
	increase(p<<1,l,r,x);
	increase(p<<1|1,l,r,x);
}
void cover(int p,int l,int r,int x){
	if(r<t[p].l||t[p].r<l) return;
	if(l<=t[p].l&&t[p].r<=r){
		t[p].v=x;
		return;
	}
	pushdown(p);
	cover(p<<1,l,r,x);
	cover(p<<1|1,l,r,x);
}
void query(int p,int l,int r){
	if(r<t[p].l||t[p].r<l) return;
	if(t[p].v){
		q.push_back({t[p].v,min(t[p].r,r)-max(t[p].l,l)+1});
		return;
	}
	query(p<<1,l,r);
	query(p<<1|1,l,r);
}
long long ksm(long long a,long long b,long long mod){
	if(!b) return 1ll;
	long long c=ksm(a,b>>1,mod);
	c=c*c%mod;
	if(b&1) c=c*a%mod;
	return c;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	build(1,1,n);
	while(m--){
		int opt,l,r,x,y;
		cin>>opt>>l>>r>>x;
		if(l>r)swap(l,r);
		if(opt==1){
			increase(1,l,r,x);
		}else if(opt==2){
			cover(1,l,r,x);
		}else if(opt==3){
			q.clear();
			query(1,l,r);
			sort(q.begin(),q.end(),[](hs a,hs b){return a.v<b.v;});
			for(hs i:q){
				if(x<=i.s){
					cout<<i.v<<"\n";
					break;
				}else{
					x-=i.s;
				}
			}
		}else{
			ans=0;
			cin>>y;
			q.clear();
			query(1,l,r);
			for(hs i:q){
				ans=(ans+i.s*ksm(i.v,x,y))%y;
			} 
			cout<<ans<<"\n";
		}
	}
	return 0;
}*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,inf=1e9+7;
int n,m,cnt,a[N],f[N];
struct node{
	int l,r,s,val,key;
	int lzinc,lzcov,cov,inc;
}t[2*N];
int rt,idx;
int newcode(int v){
	idx++;
	t[idx].l=t[idx].r=t[idx].lzinc=t[idx].lzcov=0;
	t[idx].cov=t[idx].inc=0;
	t[idx].s=1;
	t[idx].val=v;
	t[idx].key=rand();
	return idx;
}
void cover(int p,int k){
	t[p].val=t[p].cov=k;
	t[p].lzcov=1;
}
void increase(int p,int k){
	t[p].val+=k;
	t[p].inc+=k;
	t[p].lzinc=1;
}
void pushup(int p){
	if(!p) return;
	t[p].s=t[t[p].l].s+t[t[p].r].s+1;
}
void pushdown(int p){
	if(!p) return;
	if(t[p].lzcov){
		if(t[p].l) cover(t[p].l,t[p].cov);
		if(t[p].r) cover(t[p].r,t[p].cov);
		t[p].cov=t[p].lzcov=0;
	}
	if(t[p].lzinc){
		if(t[p].l) increase(t[p].l,t[p].inc);
		if(t[p].r) increase(t[p].r,t[p].inc);
		t[p].inc=t[p].lzinc=0;
	}
	return;
}
void split(int x,int &l,int &r,int k){
	if(x) pushdown(x);
	if(!x){
		l=r=0;
		return;
	}
	if(t[t[x].l].s+1<=k){
		l=x;
		split(t[x].r,t[l].r,r,k-t[t[x].l].s-1);
	}else{
		r=x;
		split(t[x].l,l,t[r].l,k);
	}
	pushup(x);
}
void merge(int x,int y,int &k){
	if(!x||!y){
		k=x+y;
		return;
	}
	if(t[x].key<t[y].key){
		pushdown(x);
		k=x;
		merge(t[x].r,y,t[x].r);
		pushup(x);
	}else{
		pushdown(y);
		k=y;
		merge(x,t[y].l,t[y].l);
		pushup(y);
	}
}
int build(int l,int r){
	if(l==r){
		return newcode(a[l]);
	}
	int x,mid=((l+r)>>1);
	merge(build(l,mid),build(mid+1,r),x);
	return x;
}
long long ksm(long long a,long long b,long long mod){
	if(!b) return 1ll;
	long long c=ksm(a,b>>1,mod);
	c=c*c%mod;
	if(b&1) c=c*a%mod;
	return c;
}
unsigned long long ans=0;
void getarr(int p){
	if(p==0){
		return;	
	}
	pushdown(p);
	getarr(t[p].l);
	f[++cnt]=t[p].val;
	getarr(t[p].r);
	return;
}
signed main(){
	freopen("kdl.in","r",stdin);
	freopen("kdl.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	srand(time(0));
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	merge(rt,build(1,n),rt);
	while(m--){
		int opt,l,r,x;
		cin>>opt>>l>>r>>x;
		if(l>r) swap(l,r);
		cnt=0;ans=0;
		memset(f,0,sizeof(f));
		if(opt==2){
			int _x,_y,_z;
			split(rt,_x,_y,l-1);
			split(_y,_y,_z,r-l+1);
			cover(_y,x);
			merge(_x,_y,_x);
			merge(_x,_z,rt);
		}else if(opt==1){
			int _x,_y,_z;
			split(rt,_x,_y,l-1);
			split(_y,_y,_z,r-l+1);
			increase(_y,x);
			merge(_x,_y,_x);
			merge(_x,_z,rt);
		}else if(opt==3){
			int _x,_y,_z;
			split(rt,_x,_y,l-1);
			split(_y,_y,_z,r-l+1);
			getarr(_y);
			sort(f+1,f+2+r-l);
			cout<<f[x]<<"\n";
			merge(_x,_y,_x);
			merge(_x,_z,rt);
		}else if(opt==4){
			long long y;
			cin>>y;
			getarr(rt);
			long long ans=0;
			for(int i=l;i<=r;i++){
				ans+=ksm(f[i],x,y);
			}
			cout<<ans%y<<"\n";
		}
	}
	return 0;
}