#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3e7+5;

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

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;
}

void modify(int l,int r,int k){
	if(pos[l]==pos[r]){
		for(int i=l;i<=r;i++) a[i]+=k;
		for(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(int i=l;i<=ed[pos[l]];i++) a[i]+=k;
		for(int i=st[pos[l]];i<=ed[pos[l]];i++) b[i]=a[i];
		sort(b+st[pos[l]],b+ed[pos[l]]);
		for(int i=pos[l]+1;i<=pos[r]-1;i++) add[i]+=k;
		for(int i=st[pos[r]];i<=r;i++) a[i]+=k;
		for(int i=st[pos[r]];i<=ed[pos[r]];i++) b[i]=a[i];
		sort(b+st[pos[r]],b+ed[pos[r]]+1);
	}
}

int check(int l,int r,int k){
	int cnt=0;
	if(pos[l]==pos[r]){
		for(int i=l;i<=r;i++) if(a[i]+add[pos[l]]<=k) cnt++;
		return cnt;
	}
	else{
		for(int i=l;i<=ed[pos[l]];i++) if(a[i]+add[pos[l]]<=k) cnt;
		for(int i=pos[l]+1;i<=pos[r]-1;i++){
			int L=st[i],R=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(L<R){
				int mid=(L+R)/2+1;
				if(b[mid]+add[i]<=k) L=mid;
				else R=mid-1;
			}
			if(b[L]+add[i]<=k) cnt+=R-st[i]+1;
		}
		for(int i=st[pos[r]];i<=r;i++) if(a[i]+add[pos[r]]<=k) cnt++;
		return cnt;
	}
	
}

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

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

int query(int l,int r,int k){
	if(k<1||k>r-l+1) return -1;
	int ans=-1,L=Min_query(l,r),R=Max_query(l,r);
	while(L<=R){
		int mid=(L+R)/2;
		if(check(L,R,mid)<k) L=mid+1;
		else R=mid-1,ans=mid;
	}
	return ans;
}

signed main(){
	cin>>n>>m;
	block=150;
	len=ceil(n*1.0/block);
	for(int i=1;i<=n;i++){
		b[i]=a[i]=read();
		pos[i]=(i-1)/block+1;
	}
	for(int i=1;i<=len;i++){
		st[i]=(i-1)*block+1;
		ed[i]=i*block;
	}
	ed[len]=n;
	for(int i=1;i<=len;i++) sort(b+st[i],b+ed[i]+1);
	for(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 modify(l,r,k);
	}
	return 0;
}