#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
namespace io {
	const int SIZE = (1 << 21) + 1;
	char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
	// getchar
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	// print the remaining part
	inline void flush () {
		fwrite (obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	// putchar
	inline void putc (char x) {
		*oS ++ = x;
		if (oS == oT) flush ();
	}
	// input a signed integer
	template <class I>
	inline void gi (I &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
	}
	// print a signed integer
	template <class I>
	inline void print (I x) {
		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
		while (qr) putc (qu[qr --]);
	}
	//no need to call flush at the end manually!
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: gi;
using io :: putc;
using io :: print;

const int N=1e5+10,M=1e5+10;
struct node{
	int id;
	long long k;
	bool operator<(const node &x)const{
		return k<x.k;
	}
}a[N],c[M],d[M],e[M];
struct kuai{
	long long l,r,maxn,minn,tag;
	kuai(){
		maxn=-1e18,minn=1e18;
	}
}b[N]; 
int n,m,len;
int ce,cc,cd,cf;
long long f[M];
int k=1;
inline void init(){
	for(int i=1;i<=n;i+=len,k++){
		b[k].l=i,b[k].r=min(i+len-1,n);
		for(int j=b[k].l;j<=b[k].r;++j){
			b[k].maxn=max(b[k].maxn,a[j].k);
			b[k].minn=min(b[k].minn,a[j].k); 
		}
		sort(a+b[k].l,a+b[k].r+1);
	}
//	for(int i=1;i<=k;++i) cout<<b[i].l<<' '<<b[i].r<<endl;
}
inline void gb(){
	ce=0;
	int pc=1,pd=1;	
	while(pc<=cc&&pd<=cd){
		if(c[pc].k<=d[pd].k) e[++ce]=c[pc++];
		else e[++ce]=d[pd++];
	}
	while(pc<=cc) e[++ce]=c[pc++];
	while(pd<=cd) e[++ce]=d[pd++];
}

inline int qk(int x){
	if(x%len==0) return x/len;
	return x/len+1;
}

inline void change(int l,int r,long long p){
	if(qk(l)==qk(r)){
		//左右两边在同一个块 
		cc=0,cd=0;
		for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i){ 
			if(l<=a[i].id&&a[i].id<=r) a[i].k+=p,c[++cc]={a[i].id,a[i].k};
			else d[++cd]={a[i].id,a[i].k};
		}
		
//		for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i) cout<<a[i].k<<' '<<a[i].id<<'\n';
//		cout<<'#'<<endl;
		
		gb();
		for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i) a[i]=e[i-b[qk(l)].l+1];
		
//		for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i) cout<<e[i-b[qk(l)].l+1].k<<' '<<e[i-b[qk(l)].l+1].id<<'\n';
//		cout<<'#'<<endl;

		b[qk(l)].maxn=a[b[qk(l)].r].k+b[qk(l)].tag,b[qk(l)].minn=a[b[qk(l)].l].k+b[qk(l)].tag;
		return;
	}
//	cout<<'C'<<L<<' '<<R<<endl;
	for(int i=qk(l)+1;i<=qk(r)-1;++i) b[i].maxn+=p,b[i].minn+=p,b[i].tag+=p;
	//左端点 l~L-1
	cc=0,cd=0;
	for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i){
		if(l<=a[i].id&&a[i].id<=r) c[++cc]={a[i].id,a[i].k+p};
		else d[++cd]={a[i].id,a[i].k};
	} 
	gb();
	for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i) a[i]=e[i-b[qk(l)].l+1];
	b[qk(l)].minn=a[b[qk(l)].l].k+b[qk(l)].tag,b[qk(l)].maxn=a[b[qk(l)].r].k+b[qk(l)].tag;
	//右端点 R+1~r
	cc=0,cd=0;
	for(int i=b[qk(r)].l;i<=b[qk(r)].r;++i){
		if(l<=a[i].id&&a[i].id<=r) c[++cc]={a[i].id,a[i].k+p};
		else d[++cd]={a[i].id,a[i].k};
	}
	gb();
	for(int i=b[qk(r)].l;i<=b[qk(r)].r;++i) a[i]=e[i-b[qk(r)].l+1];
	b[qk(r)].maxn=a[b[qk(r)].r].k+b[qk(r)].tag,b[qk(r)].minn=a[b[qk(r)].l].k+b[qk(r)].tag;
	
	//调试 
//	for(int i=1;i<=n;++i) cout<<a[i].id<<' '<<a[i].k<<" #";
//	cout<<endl;
//	for(int i=1;i<=k;++i) cout<<b[i].l<<' '<<b[i].r<<' '<<b[i].minn<<' '<<b[i].maxn<<' '<<b[i].tag<<endl;
//	cout<<'!'<<endl;
}
inline int ef(int l,int r,int x){
	while(l<=r){
		int mid=(l+r)>>1;
		if(a[mid].k>x) r=mid-1;
		else l=mid+1;
	}
	return l;
}
inline int qsum(int l,int r,long long x){
	if(qk(l)==qk(r)){
		int sum=0;
//		int k=upper_bound(a+b[qk(l)].l,a+b[qk(l)].r+1,node({100000,x-b[qk(l)].tag}))-a-1;
		int k=ef(b[qk(l)].l,b[qk(l)].r,x-b[qk(l)].tag)-1;
		for(int i=b[qk(l)].l;i<=k;i++) if(l<=a[i].k&&a[i].k<=r) sum++;
		return sum;
	}
	int sum=0;
	for(int i=qk(l)+1;i<=qk(r)-1;++i){
//		int k=upper_bound(a+b[i].l,a+b[i].r+1,node({100000,x-b[i].tag}))-a;
		int k=ef(b[i].l,b[i].r,x-b[i].tag);
		sum+=k-b[i].l;
	}
//	cout<<l<<' '<<r<<' '<<x<<' '<<sum<<endl;
	//散块暴力找
	//左 
//	int k=upper_bound(a+b[qk(l)].l,a+b[qk(l)].r+1,node({100000,x-b[qk(l)].tag}))-a-1;
	int k=ef(b[qk(l)].l,b[qk(l)].r,x-b[qk(l)].tag)-1;
	for(int i=b[qk(l)].l;i<=k;++i) 
		if(l<=a[i].id) sum++;
	//右
//	k=upper_bound(a+b[qk(r)].l,a+b[qk(r)].r+1,node({100000,x-b[qk(r)].tag}))-a-1;
	k=ef(b[qk(r)].l,b[qk(r)].r,x-b[qk(r)].tag)-1;
	for(int i=b[qk(r)].l;i<=k;++i){
		if(a[i].id<=r) sum++;
	} 
	return sum;                                                                                 
}
inline void query(int l,int r,int p){
	if(r-l+1<p){
		print(-1);
		putc('\n');
		return; 
	}
	if(qk(l)==qk(r)){ 
		if(p==1){
			long long minn=1e18;
			for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i){
				if(a[i].id>=l&&a[i].id<=r) minn=min(a[i].k+b[qk(l)].tag,minn);
			}
			print(minn);
			putc('\n');
			return;
		}
		cf=0;
		for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i) if(l<=a[i].id&&a[i].id<=r) f[++cf]=a[i].k+b[qk(l)].tag;
		sort(f+1,f+cf+1);
//		cout<<cf<<endl;	
		if(cf>=p) print(f[p]),putc('\n');
		else print(-1),putc('\n');
		return;
	}
	long long l_=1e18,r_=-1e18,ans=1e18;
//	cout<<L<<' '<<R<<endl;
	for(int i=qk(l)+1;i<=qk(r)-1;++i) l_=min(l_,b[i].minn),r_=max(r_,b[i].maxn);
//	cout<<l_<<' '<<r_<<endl;
	for(int i=b[qk(l)].l;i<=b[qk(l)].r;++i){
		if(a[i].id>=l) l_=min(l_,a[i].k+b[qk(l)].tag),r_=max(r_,a[i].k+b[qk(l)].tag);
	}
//	cout<<l_<<' '<<r_<<endl;
	for(int i=b[qk(r)].l;i<=b[qk(r)].r;++i){
		if(a[i].id<=r) l_=min(l_,a[i].k+b[qk(r)].tag),r_=max(r_,a[i].k+b[qk(r)].tag);
	}
//	cout<<l_<<' '<<r_<<endl;
	while(l_<=r_){
		int mid=(l_+r_)>>1;
		if(qsum(l,r,mid)>=p) r_=mid-1,ans=mid;
		else l_=mid+1;
	}
	if(ans!=1e18) print(ans),putc('\n');
	else print(-1),putc('\n');
}
signed main(){
	//freopen("","r",stdin);
	//freopen("","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	gi(n),gi(m);
	len=700;
	for(int i=1;i<=n;++i) gi(a[i].k),a[i].id=i;
	init();
//	for(int i=1;i<=n;++i) cout<<a[i].k<<' '<<a[i].id<<endl;
//	cout<<'#'<<endl;
//	cout<<m<<endl;
	for(int i=1;i<=m;++i){
		int op,l,r,k;
		gi(op),gi(l),gi(r),gi(k);
		if(op==1) query(l,r,k);
		else change(l,r,k);
//			cout<<'q'<<qsum(1,5,7)<<endl;
	}
	return 0;
}