#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int maxn=1e5+10;
int n,m,len,siz,a[maxn],num[maxn];
struct node{
	int id,cnt;
	
}v[maxn];
int l[maxn],r[maxn],tag[maxn];
inline void get_sort(int l,int r,int k){
	for(int i=(num[l]-1)*len+1;i<min(num[l]*len,n);++i)if(l<v[i].id && v[i].id<r)v[i].cnt+=k,a[v[i].id]+=k;
	sort(v+(num[l]-1)*len+1,v+min(num[l]*len,n)+1,[](node x,node y){return x.cnt<y.cnt;});
}
inline void add(int l,int r,int kk){
	if(num[l]==num[r]){get_sort(l,r,kk);return ;}
	for(int k=num[l]+1;k<num[r];++k)tag[k]+=kk;
	get_sort(l,num[l]*len,kk);get_sort((num[r]-1)*len+1,r,kk);
}
inline int find(int l,int r,int kk){
	if(r-l+1<kk)return -1;
	if(num[l]==num[r]){
		vector<int>e;for(int i=0;i<=r-l;++i)e.push_back(a[i+l]);
		sort(e.begin(),e.end());return e[kk-1]+tag[num[l]];
	}
	int L=-2*10*10*10*10,R=2*10*10*10*10;
	while(l<r){
		int mid=(L+R)/2;int cnt=0;
		for(int k=num[l]+1;k<num[r];++k){
			if(v[k*len].cnt+tag[k]<=mid)cnt+=len;
			else if(v[(k-1)*len+1].cnt+tag[k]<=mid){
				int l1=(k-1)*len+1,r1=k*len;
				while(l1<r1){
					int mid=(l1+r1)/2;
					if(v[mid].cnt+tag[kk]>mid)r1=mid-1;
					else l1=mid;
				}
				cnt+=l1-(k-1)*len-1;
			}
		}
		for(int k=l;k<num[l]*len;++k)if(a[k]+tag[num[k]]<=mid)++cnt;
		for(int k=((num[r]-1)*len+1);k<=r;++k)if(a[k]+tag[num[r]]<=mid)++cnt;
		if(cnt>=kk)r=mid;
		else l=mid+1;
	}
	return l;
}
signed main(){
	scanf("%lld%lld",&n,&m);len=sqrt(n);for(int i=1;i<=n;++i){scanf("%lld",a+i);v[i].id=i,v[i].cnt=a[i];num[i]=(i-1)/len+1;}
	siz=n/len;if(n%len!=0)siz++;for(int i=1;i<siz;++i){sort(v+((i-1)*len+1),v+(i*len)+1,[](node x,node y){return x.cnt<y.cnt;});}
	sort(v+n-len+1,v+n+1,[](node x,node y){return x.cnt<y.cnt;});
	for(int i=1;i<=m;++i){int op,l,r,k;scanf("%lld%lld%lld%lld",&op,&l,&r,&k);if(op==1)printf("%lld\n",find(l,r,k));else add(l,r,k);}	
	return 0;
}