#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=10000010;
ll a[maxn],t[maxn],belong[maxn],st[maxn],ed[maxn],siz[maxn],tag[maxn];
ll n,m,block=150,len;
ll read(){
   ll 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 init()
{
	block=150;
	len = ceil(n * 1.0 / block);
	for(ll i=1;i<=len;i++)
	{
		st[i]=(i-1)*len+1;
		ed[i]=i*len;
		siz[i]=ed[i]-st[i]+1;
	}
	ed[len]=n;
	for(ll i=1;i<=len;i++)
	{
		for(ll j=st[i];j<=ed[i];j++)
		{
			belong[j]=i;
		}
		sort(t+st[i],t+ed[i]+1);
	}
}
ll check(ll l,ll r,ll w)
{
	ll x=belong[l],y=belong[r];
	ll cnt=0;
	if(x==y)
	{
		for(ll i=l;i<=r;i++)
		{
			if(a[i]+tag[x]<=w) cnt++;
		}
		return cnt;
	}
	for(ll i=l;i<=ed[x];i++)
	{
		if(a[i]+tag[x]<=w) cnt++;
	}
	for(ll i=st[y];i<=r;i++)
	{
		if(a[i]+tag[x]<=w) cnt++;
	}
	for(ll i=x+1;x<y;i++)
	{
		if(t[st[i]]+tag[i]>w) continue;
		if(t[ed[i]]+tag[i]<=w) 
		{
			cnt+=ed[i]-st[i]+1;
			continue;
		}
		ll L=st[i],rr=ed[i];
		while(L<rr)
		{
			ll mid=L+rr>>1+1;
			if(t[L]+tag[i]<=w) L=mid;
			else rr=mid-1;
		}
		if(t[L]+tag[i]<=w)	cnt+=L-st[i]+1;
	}
	return cnt;
}
ll getmax(ll l,ll r)
{
	ll x=belong[l],y=belong[r];
	ll ans=-100000000;
	if(x==y)
	{
		for(ll i=l;i<=r;i++){
			ans=max(ans,a[i]+tag[x]);
		}
		return ans;
	}
	for(ll i=l;i<=ed[x];i++)
	{
		ans=max(ans,a[i]+tag[x]);
	}
	for(ll i=st[y];i<=r;i++){
		ans=max(ans,a[i]+tag[y]); 
	}
	for(ll i=x+1;i<y;i++){
		ans=max(ans,t[ed[i]]+tag[i]);
	}return ans;
}
ll getmin(ll l,ll r)
{
	ll x=belong[l],y=belong[r];
	ll ans=maxn<<1;
	if(x==y)
	{
		for(ll i=l;i<=r;i++){
			ans=min(ans,a[i]+tag[x]);
		}
		return ans;
	}
	for(ll i=l;i<=ed[x];i++)
	{
		ans=min(ans,a[i]+tag[x]);
	}
	for(ll i=st[y];i<=r;i++){
		ans=min(ans,a[i]+tag[y]); 
	}
	for(ll i=x+1;i<y;i++){
		ans=min(ans,t[st[i]]+tag[i]);
	}return ans;
}
void change(ll l,ll r,ll k)
{
	ll x=belong[l],y=belong[r];
	if(x==y)
	{
		for(ll i=l;i<=r;i++){
			a[i]+=k;
		}
		for(ll i=st[x];i<=ed[x];i++){
			t[i]=a[i];
		}
		sort(t+st[x],t+ed[x]+1);
		return;
	}
	for(ll i=l;i<=ed[x];i++){
		a[i]+=k;
	}for(ll i=st[y];i<=r;i++){
		a[i]+=k; 
	}for(ll i=x+1;i<y;i++){
		tag[i]+=k;
	}for(ll i=st[x];i<=ed[x];i++) t[i]=a[i];
	sort(t+st[x],t+ed[x]+1);
	for(ll i=st[y];i<=ed[y];i++) t[i]=a[i];
	sort(t+st[y],t+ed[y]+1);
}
ll query(ll x,ll y,ll k)
{
	if(k<1||k>y-x+1) return -1;
	ll l,r,mid;
	ll ans=-1;
	l=getmin(x,y);
	r=getmax(x,y);
	while(l<=r)
	{
		ll mid=l+r>>1;
		if(check(x,y,mid)<k) l=mid+1;
		else 
		{
			r=mid-1;
			ans=mid;
		}
	}
	return ans;
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++)
	{
		a[i]=read();
		t[i]=a[i];
	}
	init();
	for(ll i=1;i<=m;i++)
	{
		ll tmp,l,r,k;
		tmp=read();
		l=read();
		r=read();
		k=read();
		if(tmp==1)
		{
			printf("%lld",query(l,r,k));
		}
		else 
		{
			change(l,r,k);
		}
	}
	return 0;
}