#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,t[N<<2],a[N],tag1[N<<2],tag2[N<<2];
bool setTag2[N<<2];
void build(int p,int l,int r){
	if(l==r){ t[p]=a[l]	return; }
	int mid=(l+r)>>1;
	build(p<<1,l,mid); build(p<<1|1,mid+1,r);
	t[p]=t[p<<1]+t[p<<1|1];
}
void add2(int p,int l,int r,int d){
	tag1[p]=0;
	t[p]=(r-l+1)*d;
	tag2[p]=d;
	setTag2[p]=true;
}
void add1(int p,int l,int r,int d){
	t[p]=t[p]+(r-l+1)*d;
	if(setTag2[p]){
		tag2[p]+=d;
	} else {
		tag1[p]+=d;
	}
}
void push_down(int p,int l,int r){
	int mid=(l+r)>>1;
	if(setTag2[p]){
		add2(p<<1, l, mid, tag2[p]);
		add2(p<<1|1, mid+1, r, tag2[p]);
		setTag2[p]=false;
		tag2[p]=0;
	}
	if(tag1[p]){
		add1(p<<1, l, mid, tag1[p]);
		add1(p<<1|1, mid+1, r, tag1[p]);
		tag1[p]=0;
	}
}
void up1(int p,int l,int r,int L,int R,int d){
	if(L<=l&&R>=r){add1(p,l,r,d); return;}
	int mid=(l+r)>>1;
	push_down(p,l,r);
	if(L<=mid) up1(p<<1,l,mid,L,R,d);
	if(R>mid) up1(p<<1|1,mid+1,r,L,R,d);
	t[p]=t[p<<1]+t[p<<1|1];
}
void up2(int p,int l,int r,int L,int R,int d){
	if(L<=l&&R>=r){add2(p,l,r,d); return;}
	int mid=(l+r)>>1;
	push_down(p,l,r);
	if(L<=mid) up2(p<<1,l,mid,L,R,d);
	if(R>mid) up2(p<<1|1,mid+1,r,L,R,d);
	t[p]=t[p<<1]+t[p<<1|1];
}
int query(int p,int l,int r,int x){
	if(l==r) return t[p];
	int mid=(l+r)>>1;
	push_down(p,l,r);
	if(x<=mid) return query(p<<1,l,mid,x);
	else return query(p<<1|1,mid+1,r,x);
}
int qpow(int x,int y,int mod){
	int res=1%mod;
	x%=mod;
	while(y){
		if(y&1) res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
int b[N],cnt;
signed main(){
	freopen("kdl.in","r",stdin);
	freopen("kdl.out","w",stdout); 
	scanf("%lld%lld",&n,&m);
	for(int i = 1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,1,n);
	while(m--){
		int op,l,r,x,y;
		scanf("%lld%lld%lld%lld",&op,&l,&r,&x);
		if(l>r) swap(l,r); 
		if(op==1) up1(1,1,n,l,r,x);
		if(op==2) up2(1,1,n,l,r,x);
		if(op==3){
			cnt=0;
			for(int i = l;i<=r;i++)
				b[++cnt]=query(1,1,n,i);
			sort(b+1,b+1+cnt);
			printf("%lld\n",b[x]);
		}
		if(op==4){
			scanf("%lld",&y);
			int res=0;
			for(int i = l;i<=r;i++)
				res=(res+qpow(query(1,1,n,i),x,y))%y;
			printf("%lld\n",res);
		}
	}
	return 0;
}