#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10,I=0x3f3f3f3f;
int len,loc[N];
int n,m,op,ll,rr,kk;
int l[N],r[N],a[N],blo,c[N];
int add[N];
vector<int>v[N];
void gai(int x,int y,int k) {
	int lo=loc[x],ro=loc[y];
	if(lo==ro) {
		v[lo].clear();
		for(int i=x; i<=y; i++) {
			a[i]+=k;
		}
		for(int i=l[lo]; i<=r[lo]; i++) {
			v[lo].push_back(a[i]);
		}
		sort(v[lo].begin(),v[lo].end());
		return;
	}
	v[lo].clear();
	for(int i=x; i<=r[lo]; i++) {
		a[i]+=k;
	}
	for(int i=l[lo]; i<=r[lo]; i++) {
		v[lo].push_back(a[i]);
	}
	sort(v[lo].begin(),v[lo].end());
	v[ro].clear();
	for(int i=l[ro]; i<=y; i++) {
		a[i]+=k;
	}
	for(int i=l[ro]; i<=r[ro]; i++) {
		v[ro].push_back(a[i]);
	}
	sort(v[ro].begin(),v[ro].end());
	for(int i=lo+1; i<=ro-1; i++) {
		add[i]+=k;
	}
}
int check(int x,int y,int k) {
	int res=0;
	int lo=loc[x],ro=loc[y];
	if(lo==ro) {
		for(int i=x; i<=y; i++) {
			if(a[i]+add[lo]<=k)res++;
		}
		return res;
	}
	for(int i=x; i<=r[lo]; i++) {
		if(a[i]+add[lo]<=k)res++;
	}
	for(int i=l[ro]; i<=y; i++) {
		if(a[i]+add[ro]<=k)res++;
	}
	for(int i=lo+1; i<=ro-1; i++) {
		res+=upper_bound(v[i].begin(),v[i].end(),k-add[i])-v[i].begin();
	}
	return res;
}
int answer(int x,int y,int k) {
	if(y-x+1<k)return -1;
//	int l1=I,r1=-I;
	int lo=loc[x],ro=loc[y];
	if(lo==ro) {
		int cnt=0;
		memset(c,0,sizeof(c));
		for(int i=x; i<=y; i++) {
			c[++cnt]=a[i]+add[lo];
		}
		sort(c+1,c+1+cnt);
		return c[k];
	} 
	int l1=-2e9,r1=2e9;
	while(l1<r1) {
		int mid=(l1+r1)>>1;
		if(check(x,y,mid)<k)l1=mid+1;
		else r1=mid;
	}
	return l1;
}
inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')
		x=x*10+ch-'0',ch=getchar();
	return x*f;
}
void write(int x) {
	if(x<0)
		putchar('-'),x=-x;
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
	return;
}
signed main() {
	n=read(),m=read();
	len=sqrt(n);
//	len=320;
	blo=(n-1)/len+1;
	for(int i=1; i<=n; i++) {
		a[i]=read();
		loc[i]=(i-1)/len+1;
		l[loc[i]]=(loc[i]-1)*len+1;
		r[loc[i]]=min(n,loc[i]*len);
		v[loc[i]].push_back(a[i]);
	}
	for(int i=1; i<=blo; i++) {
		sort(v[i].begin(),v[i].end());
	}
	while(m--) {
		op=read(),ll=read(),rr=read(),kk=read();
		if(op==2) {
			gai(ll,rr,kk);
		} else {
			write(answer(ll,rr,kk));
			cout<<"\n";
		}
	}
	return 0;
}