#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

#define N 100005 
#define int long long

int n,m,size,cnt,len3,len4,len5;
int id[N],l[N],r[N],a[N],tag[N];
pair<int,int> b[N],v1[N],v2[N],v3[N],v4[N],v5[N];

void add(int x,int y,int k){
	int lb=id[x],rb=id[y],len1=0,len2=0;
	for(int i=l[lb];i<=r[lb];i++){
		if(b[i].second>=x&&b[i].second<=y){
			v1[++len1]=b[i];
			v1[len1].first+=k;
		}
		else{
			v2[++len2]=b[i];
		}
	}
	merge(v1+1,v1+len1+1,v2+1,v2+len2+1,b+l[lb]);
	if(lb==rb) return ;
	len1=0,len2=0;
	for(int i=l[rb];i<=r[rb];i++){
		if(b[i].second>=x&&b[i].second<=y){
			v1[++len1]=b[i];
			v1[len1].first+=k;
		}
		else{
			v2[++len2]=b[i];
		}
	}
	merge(v1+1,v1+len1+1,v2+1,v2+len2+1,b+l[rb]);
	for(int i=lb+1;i<=rb-1;i++) tag[i]+=k;
}

void init(){
	if(n==1) size=1;
	else size=sqrt(n*log2(n));
	for(int i=1;i<=n;i++) id[i]=(i-1)/size+1;
	for(int i=1;i<=n;i++) l[i]=(i-1)*size+1,r[i]=i*size;
	cnt=n/size;
	if(cnt*size!=n) cnt++;
	r[cnt]=min(r[cnt],n);
	for(int i=1;i<=cnt;i++){
		sort(b+l[i],b+r[i]+1);
	}
}

int getrank(int x,int y,int k){
	int lb=id[x],rb=id[y],tot=0;
	if(lb==rb){
		int dis=lower_bound(v5+1,v5+1+len5,make_pair(k-tag[lb],0ll))-v5;
		return dis-1;
	}
	tot+=lower_bound(v3+1,v3+1+len3,make_pair(k-tag[lb],0ll))-v3,tot--;
	tot+=lower_bound(v4+1,v4+1+len4,make_pair(k-tag[rb],0ll))-v4,tot--;
	for(int i=lb+1;i<=rb-1;i++){
		tot+=lower_bound(b+l[i],b+r[i]+1,make_pair(k-tag[i],0ll))-b,tot--;
	}
	return tot;
}

void init1(int x,int y,int k){
	int lb=id[x],rb=id[y];
	len3=0,len4=0,len5=0;
	if(lb==rb){
		for(int i=l[lb];i<=r[lb];i++){
			if(b[i].second>=x&&b[i].second<=y){
				v5[++len5]=b[i];
			}
		}
	}
	else{
		for(int i=l[lb];i<=r[lb];i++){
			if(b[i].second>=x&&b[i].second<=y){
				v3[++len3]=b[i];
			}
		}
		for(int i=l[rb];i<=r[rb];i++){
			if(b[i].second>=x&&b[i].second<=y){
				v4[++len4]=b[i];
			}
		}
	}
}

signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		b[i].first=a[i];
		b[i].second=i;
	}
	init();
	while(m--){
		int op,x,y,k;
		scanf("%lld",&op);
		if(op==1){
			scanf("%lld%lld%lld",&x,&y,&k);
			if(k<1||k>(y-x+1)){
				printf("-1\n");
				continue;
			}
			int l=-3e9-1,r=3e9+1,ans=0;
			init1(x,y,k);
			while(l<=r){
				int mid=l+r>>1,now=getrank(x,y,mid);
				if(now<k){
					ans=mid;
					l=mid+1;
				}
				else{
					r=mid-1;
				}
			}
			printf("%lld\n",ans);
		}
		else{
			scanf("%lld%lld%lld",&x,&y,&k);
			add(x,y,k);
		}
	}
	return 0;
}