#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,a[N],op,x,y,k,maxn[N],minn[N],len,id[N],tag[N],sl[N],sr[N],b[N];
int get_min(int x,int y)
{
	int l=id[x],r=id[y];
	int ans=INT_MAX;
	if(l==r)
	{
		for(int i=x;i<=y;i++)ans=min(ans,a[i]+tag[l]);
	}
	else
	{
		for(int i=x;i<=l*len;i++)ans=min(ans,a[i]+tag[l]);
		for(int i=r*len-len+1;i<=y;i++)ans=min(ans,a[i]+tag[r]);
		for(int i=l+1;i<r;i++)ans=min(ans,minn[i]+tag[i]);
	}
	return ans;
}
int get_max(int x,int y)
{
	int l=id[x],r=id[y];
	int ans=INT_MIN;
	if(l==r)
	{
		for(int i=x;i<=y;i++)ans=max(ans,a[i]+tag[l]);
	}
	else
	{
		for(int i=x;i<=l*len;i++)ans=max(ans,a[i]+tag[l]);
		for(int i=r*len-len+1;i<=y;i++)ans=max(ans,a[i]+tag[r]);
		for(int i=l+1;i<r;i++)ans=max(ans,maxn[i]+tag[i]);
	}
	return ans;
}
bool check(int mid)
{
	int l=id[x],r=id[y];
	if(l==r)
	{
		int ans=0;
		for(int i=x;i<=y;i++)ans+=(a[i]+tag[l]<=mid);
		return ans>=k;
	}
	else
	{
		int ans=0;
		for(int i=x;i<=l*len;i++)ans+=(a[i]+tag[id[i]]<=mid);
		for(int i=r*len-len+1;i<=y;i++)ans+=(a[i]+tag[id[i]]<=mid);
		for(int i=l+1;i<r;i++)
		{
			if(minn[i]+tag[i]>mid)continue;
			ans+=upper_bound(b+sl[i],b+sr[i]+1,mid-tag[i])-b-sl[i];
		}
		return ans>=k;
	}
}
int florr(int x)
{
	int ans=x/2;
	if(x<0&&x%2!=0)return ans-1;
	else return ans;
}
int read()
{
    int x=0,f=1;
    char ch=getchar_unlocked();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar_unlocked();
    }
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch&15),ch=getchar_unlocked();
    return x*f;
}
signed main()
{
	ios::sync_with_stdio(0);
	cout.tie(0);
	n=read(),m=read();
	len=sqrt(n);
	for(int i=1;i<=n;i++)id[i]=(i+len-1)/len;
	for(int i=1;i<=n;i++)a[i]=read(),b[i]=a[i];
	for(int i=1;i<=id[n];i++)maxn[i]=INT_MIN,minn[i]=INT_MAX,sl[i]=1e9;
    for(int i=1;i<=n;i++)maxn[id[i]]=max(maxn[id[i]],a[i]),minn[id[i]]=min(minn[id[i]],a[i]);
	for(int i=1;i<=n;i++)sl[id[i]]=min(sl[id[i]],i),sr[id[i]]=max(sr[id[i]],i);
	for(int i=1;i<=id[n];i++)sort(b+sl[i],b+sr[i]+1);
	while(m--)
	{
		op=read(),x=read(),y=read(),k=read();
		if(op==1)
		{
			if(k>y-x+1)
			{
				cout<<-1<<"\n";
				continue;
			}
			int l=get_min(x,y);
			int r=get_max(x,y);
			while(l<r)
			{
				int mid=florr(l+r);
				if(check(mid))r=mid;
				else l=mid+1;
			}
			cout<<r<<"\n";
		}
		else
		{
			int l=id[x],r=id[y];
			int ans=INT_MIN;
			if(l==r)
			{
				minn[l]=INT_MAX;
				maxn[l]=INT_MIN; 
				for(int i=sl[l];i<=sr[l];i++)
				{
					if(x<=i&&i<=y)a[i]+=k;
					minn[l]=min(minn[l],a[i]);
					maxn[l]=max(maxn[l],a[i]);
					b[i]=a[i];
				}
				sort(b+sl[l],b+sr[l]+1);
			}
			else
			{
				minn[l]=INT_MAX;
				maxn[l]=INT_MIN; 
				for(int i=sl[l];i<=sr[l];i++)
				{
					if(x<=i)a[i]+=k;
					minn[l]=min(minn[l],a[i]);
					maxn[l]=max(maxn[l],a[i]);
					b[i]=a[i];
				}
				sort(b+sl[l],b+sr[l]+1);
				minn[r]=INT_MAX;
				maxn[r]=INT_MIN; 
				for(int i=sl[r];i<=sr[r];i++)
				{
					if(i<=y)a[i]+=k;
					minn[r]=min(minn[r],a[i]);
					maxn[r]=max(maxn[r],a[i]);
					b[i]=a[i];
				}
				sort(b+sl[r],b+sr[r]+1);
				for(int i=l+1;i<r;i++)tag[i]+=k;
			}
		}
	}
	return 0;
}
/*
10 3 -26 0 2 5 10 -6 -14 2
*/