#include<bits/stdc++.h>
#define int long long
using namespace std;
int block,tot,n,lt[1005],rt[1005],a[100005],lazy[1005],belong[100005],d[100005],m;
void build(){
	block=(int)sqrt((double)n);
	tot=n/block;
	if(n%block) tot++;
	for(int i=1;i<=tot;i++){
		lt[i]=(i-1)*block+1;
		rt[i]=i*block;
	}
	rt[tot]=n;
	for(int i=1;i<=n;i++) belong[i]=(i-1)/block+1;
	for(int i=1;i<=n;i++) d[i]=a[i];
	for(int i=1;i<=tot;i++) sort(a+lt[i],a+rt[i]);
}
void change(int x,int y,int k){
	if(belong[x]==belong[y]){
		for(int i=x;i<=y;i++)a[i]+=k;
		for(int i=lt[belong[x]];i<=rt[belong[x]];i++)d[i]=a[i];
		sort(d+lt[belong[x]],d+rt[belong[x]]);
		return;
	}
	for(int i=x;i<=rt[belong[x]];i++)a[i]+=k;
	for(int i=lt[belong[x]];i<=rt[belong[x]];i++)d[i]=a[i];
	sort(d+lt[belong[x]],d+rt[belong[x]]);
	for(int i=lt[belong[y]];i<=y;i++)a[i]+=k;
	for(int i=lt[belong[y]];i<=rt[belong[y]];i++)d[i]=a[i];
	sort(d+lt[belong[y]],d+rt[belong[y]]);
	for(int i=belong[x]+1;i<=belong[y]-1;i++)lazy[i]+=k;
	return;
}
int ask(int x,int y,int k){
	if(belong[x]==belong[y]){
		int l=-1e9,r=1e9,ans=0;
		while(l<=r){
			int mid=(l+r)>>1,res=0;
			for(int i=x;i<=y;i++)if(a[i]+lazy[belong[x]]<mid)res++;
			if(res<k) l=mid+1,ans=mid;
			else  r=mid-1;
		}
		if(ans==1e9) return -1;
		else return ans;
	}
	int l=-1e9,r=1e9,ans=0;
	while(l<=r){
		int mid=(l+r)>>1,res=0;
		for(int i=x;i<=rt[belong[x]];i++) if(a[i]+lazy[belong[x]]<mid)res++;
		for(int i=lt[belong[y]];i<=y;i++) if(a[i]+lazy[belong[y]]<mid)res++;
		for(int i=belong[x]+1;i<=belong[y]-1;i++) res+=lower_bound(d+lt[i],d+rt[i],mid-lazy[i])-d-lt[i];
		if(res<k) l=mid+1,ans=mid;
		else r=mid-1;
	}
	if(ans==1e9) return -1;
	else return ans;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build();
	for(int i=1;i<=m;i++){
		int opt,l,r,w;
		cin>>opt;
		if(opt==2){
			cin>>l>>r>>w;
			change(l,r,w);
		}
		else{
			cin>>l>>r>>w;
			cout<<ask(l,r,w)<<endl;
		}
	}
	return 0;
}