#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6+5;

int n,m,block,len;
int st[maxn],ed[maxn],pos[maxn],a[maxn],b[maxn],add[maxn];

inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}

inline void update(int l,int r,int k){
	if(pos[l]==pos[r]){
		for(register int i=l;i<=r;i++) a[i]+=k;
		for(register int i=st[pos[l]];i<=ed[pos[l]];i++) b[i]=a[i];
		sort(b+st[pos[l]],b+ed[pos[l]]+1);
	}
	else{
		for(register int i=l;i<=ed[pos[l]];i++) a[i]+=k;
		for(register int i=st[pos[l]];i<=ed[pos[l]];i++) b[i]=a[i];
		sort(b+st[pos[l]],b+ed[pos[l]]+1);
		for(register int i=pos[l]+1;i<=pos[r]-1;i++) add[i]+=k;
		for(register int i=st[pos[r]];i<=r;i++) a[i]+=k;
		for(register int i=st[pos[r]];i<=ed[pos[r]];i++) b[i]=a[i];
		sort(b+st[pos[r]],b+ed[pos[r]]+1);
	}
}

inline int check(int l,int r,int k){
	int cnt=0;
	if(pos[l]==pos[r]){
		for(register int i=l;i<=r;i++) if(a[i]+add[pos[l]]<=k) cnt++;
		return cnt;
	}
	else{
		for(register int i=l;i<=ed[pos[l]];i++) if(a[i]+add[pos[l]]<=k) cnt++;
		for(register int i=pos[l]+1;i<=pos[r]-1;i++){
			int ll=st[i],rr=ed[i];
			if(b[st[i]]+add[i]>k)continue;
			if(b[ed[i]]+add[i]<=k){
				cnt+=ed[i]-st[i]+1;
				continue;
			}
			while(ll<rr){
				int mid=(ll+rr)/2+1;
				if(b[mid]+add[i]<=k) ll=mid;
				else rr=mid-1;
			}
			if(b[ll]+add[i]<=k) cnt+=ll-st[i]+1;
		}
		for(register int i=st[pos[r]];i<=r;i++) if(a[i]+add[pos[r]]<=k) cnt++;
		return cnt;	
	}
}

inline int getmin(int l,int r){
	int ans=2e9;
	if(pos[l]==pos[r]){
		for(register int i=l;i<=r;i++) ans=min(ans,a[i]+add[pos[i]]);
		return ans;
	}
	else{
		for(register int i=l;i<=ed[pos[l]];i++) ans=min(ans,a[i]+add[pos[i]]);
		for(register int i=pos[l]+1;i<=pos[r]-1;i++) ans=min(ans,b[st[i]]+add[i]);
		for(register int i=st[pos[r]];i<=r;i++) ans=min(ans,a[i]+add[pos[i]]);
		return ans;
	}
}

inline int getmax(int l,int r){
	int ans=-2e9;
	if(pos[l]==pos[r]){
		for(register int i=l;i<=r;i++) ans=max(ans,a[i]+add[pos[i]]);
		return ans;
	}
	else{
		for(register int i=l;i<=ed[pos[l]];i++) ans=max(ans,a[i]+add[pos[i]]);
		for(register int i=pos[l]+1;i<=pos[r]-1;i++) ans=max(ans,b[ed[i]]+add[i]);
		for(register int i=st[pos[r]];i<=r;i++) ans=max(ans,a[i]+add[pos[i]]);
		return ans;
	}
}

inline int query(int l,int r,int k){
	if(k<1||k>r-l+1) return -1;
	int ans=-1,ll=getmin(l,r),rr=getmax(l,r);
	while(ll<=rr){
		int mid=(ll+rr)/2;
		if(check(ll,rr,mid)<k) ll=mid+1;
		else rr=mid-1,ans=mid;
	}
	return ans;
} 

signed main(){
	n=read(),m=read();
	block=150;
	len=ceil(n*1.0/block);
	for(register int i=1;i<=n;i++){
		b[i]=a[i]=read();
		pos[i]=(i-1)/block+1;
	}
	for(register int i=1;i<=len;i++){
		st[i]=(i-1)*block+1;
		ed[i]=i*block;
	}
	ed[len]=n;
	for(register int i=1;i<=len;i++) sort(b+st[i],b+ed[i]+1);
	for(register int i=1,op,l,r,k;i<=m;i++){
		op=read(),l=read(),r=read(),k=read();
		if(op==1) printf("%lld\n",query(l,r,k));
		else update(l,r,k);
	}
	return 0;
}