#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[114514];
int size,belong[114514],bl[114514],br[114514],bnum;
int val[114514];
int lazy[114514];
int lower(int b,int x)
{
	int l=bl[b],r=br[b];
	int res=0;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(val[mid]<x)
			l=mid+1,res=mid;
		else
			r=mid-1;
	}
	return res;
}
void bld()
{
	size=sqrt(n);
	bnum=ceil(1.0*n/size);
	for(int i=1;i<=bnum;i++)
	{
		bl[i]=(i-1)*size+1;
		br[i]=i*size;
		for(int j=bl[i];j<=br[i];j++)
			belong[j]=i;
	}
	belong[bnum]=n;
	for(int i=1;i<=n;i++)
		val[i]=a[i];
	for(int i=1;i<=bnum;i++)
		sort(val+bl[i]+1,val+br[i]+1);
}
int query(int l,int r,int k)
{
	if(belong[l]==belong[r])
		return val[l+k-1];
	int L=0,R=114514;
	int res=0;
	while(L<=R)
	{
		int mid=(L+R)/2;
		int cnt=0;
		for(int i=l;i<=br[belong[l]];i++)
			cnt+=(a[i]+lazy[belong[l]])<mid;
		for(int i=bl[belong[r]];i<=r;i++)
			cnt+=(a[i]+lazy[belong[r]])<mid;
		for(int i=belong[l]+1;i<=belong[r]-1;i++)
			cnt+=lower(i,mid);
		if(cnt<mid)	
			L=mid+1,res=mid;
		else
			R=mid-1;
	}
	return res;
}
void add(int l,int r,int k)
{
	if(belong[l]==belong[r])
	{
		for(int i=l;i<=r;i++)
			a[i]+=k;
		for(int i=bl[belong[l]];i<=br[belong[l]];i++)
			val[i]=a[i]+lazy[belong[l]];
		sort(val+bl[belong[l]]+1,val+br[belong[l]]+1);
		return;
	}
	for(int i=l;i<=br[belong[l]];i++)
		a[i]+=k;
	for(int i=bl[belong[l]];i<=br[belong[l]];i++)
		val[i]=a[i]+lazy[belong[l]];
	sort(val+bl[belong[l]]+1,val+br[belong[l]]+1);
	
	for(int i=bl[belong[r]];i<=r;i++)
		a[i]+=k;
	for(int i=bl[belong[r]];i<=br[belong[r]];i++)
		val[i]=a[i]+lazy[belong[r]];
	sort(val+bl[belong[r]]+1,val+br[belong[r]]+1);
	
	for(int i=belong[l]+1;i<=belong[r]-1;i++)
		lazy[i]+=k;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	bld();
	while(m--)
	{
		int op,l,r,k;
		cin>>op>>l>>r>>k;
		if(op==1)
		{
			if(r-l+1<k)
			{
				cout<<-1;
				continue;
			}
			cout<<query(l,r,k)<<endl;
		}
		else
			add(l,r,k);
	}
}