#include<bits/stdc++.h>
#define blk(i) ((((i)-1)/B)+1)
#define lft(i) ((((i)-1)*B)+1)
#define rgt(i) min((i)*B,n)
using namespace std;
const int N=100005,Bl=80;
int n,m,B,a[N],b[N],mx[Bl],mn[Bl],lz[Bl];
void reset(int u)
{
	for(int i=lft(u);i<=rgt(u);i++)b[i]=a[i];
	sort(b+lft(u),b+rgt(u)+1);
	mn[u]=b[lft(u)];mx[u]=b[rgt(u)];
}
void update(int l,int r,int k)
{
	int L=blk(l),R=blk(r);
	if(L==R)
	{
		for(int i=l;i<=r;i++)a[i]+=k;
		reset(L);
		return;
	}
	for(int i=L+1;i<R;i++)lz[i]+=k;
	for(int i=l;blk(i)==L;i++)a[i]+=k;
	for(int i=r;blk(i)==R;i--)a[i]+=k;
	reset(L);reset(R);
}
bool check(int l,int r,int k,int x)
{
	int L=blk(l),R=blk(r),res=0;
	if(L==R)
	{
		for(int i=l;i<=r;i++)if(a[i]+lz[L]<=x)res++;
		return res>=k;
	}
	for(int i=L+1;i<R;i++)res+=upper_bound(b+lft(i),b+rgt(i)+1,x-lz[i])-b-lft(i);
	for(int i=l;blk(i)==L;i++)if(a[i]+lz[L]<=x)res++;
	for(int i=r;blk(i)==R;i--)if(a[i]+lz[R]<=x)res++;
	return res>=k;
}
int query(int l,int r,int k)
{
	if(k>r-l+1)return -1;
	int bl=INT_MAX,br=INT_MIN,L=blk(l),R=blk(r),ans,mid;
	for(int i=L+1;i<R;i++)bl=min(bl,mn[i]+lz[i]),br=max(br,mx[i]+lz[i]);
	for(int i=l;blk(i)==L;i++)bl=min(bl,a[i]+lz[L]),br=max(br,a[i]+lz[L]);
	for(int i=r;blk(i)==R;i--)bl=min(bl,a[i]+lz[R]),br=max(br,a[i]+lz[R]);
	while(bl<=br)
	{
		mid=(long long)bl+(long long)br>>1;
		if(check(l,r,k,mid))
		{
			br=mid-1;
			ans=mid;
		}
		else bl=mid+1;
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	B=sqrt(n/max(log2(n),1.0));
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=blk(n);i++)reset(i);
	for(int i=1,op,l,r,k;i<=m;i++)
	{
		cin>>op>>l>>r>>k;
		if(op^1)update(l,r,k);
		else cout<<query(l,r,k)<<'\n';
	}
}

WA+T