#include<bits/stdc++.h>
using namespace std;
/* --------------- fast io --------------- */ // begin
namespace Fread
{
	const int SIZE=1<<21;
	char buf[SIZE],*S,*T;
	inline char getchar()
	{
		if(S==T)
		{
			T=(S=buf)+fread(buf,1,SIZE,stdin);
			if(S==T) 
				return EOF;
		}
		return *S++;
	}
}
namespace Fwrite
{
	const int SIZE=1<<21;
	char buf[SIZE],*S=buf,*T=buf+SIZE;
	inline void flush()
	{
		fwrite(buf,1,S-buf,stdout);
		S=buf;
	}
	inline void putchar(char c)
	{
		*S++=c;
		if(S==T)
			flush();
	}
	struct NTR
	{
		~NTR()
		{
			flush();
		}
	}ztr;
}
#define getchar Fread::getchar
#define putchar Fwrite::putchar
namespace Fastio
{
	struct Reader
	{
		template<typename T>
		Reader& operator >> (T&x)
		{
			char c=getchar();
			T f=1;
			while(c<'0'||c>'9')
			{
				if(c=='-')
					f=-1;
				c=getchar();
			}
			x=0;
			while(c>='0'&&c<='9')
			{
				x=x*10+(c - '0');
				c=getchar();
			}
			x*=f;
			return *this;
		}
		Reader& operator >> (char& c)
		{
			c=getchar();
			while(c=='\n'||c==' ') 
				c=getchar();
			return *this;
		}
		Reader& operator >> (char* str)
		{
			int len=0;
			char c=getchar();
			while(c=='\n'||c==' ')
				c=getchar();
			while(c!='\n'&&c!=' ')
			{
				str[len++]=c;
				c=getchar();
			}
			str[len]='\0';
			return *this;
		}
		Reader(){}
	}cin;
	const char endl='\n';
	struct Writer
	{
		template<typename T>
		Writer& operator << (T x)
		{
			if(x==0) 
			{
				putchar('0');
				return *this;
			}
			if(x<0)
			{
				putchar('-');
				x=-x;
			}
			static int sta[45];
			int top=0;
			while(x)
			{
				sta[++top]=x%10;
				x/=10;
			}
			while(top)
			{
				putchar(sta[top]+'0');
				--top;
			}
			return *this;
		}
		Writer& operator << (char c)
		{
			putchar(c);
			return *this;
		}
		Writer& operator << (char* str)
		{
			int cur = 0;
			while(str[cur]) 
				putchar(str[cur++]);
			return *this;
		}
		Writer& operator << (const char* str)
		{
			int cur = 0;
			while(str[cur])
				putchar(str[cur++]);
			return *this;
		}
		Writer(){}
	}cout;
}
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
/* --------------- fast io --------------- */ // end
int n,m;
int a[114514];
int size,belong[114514],bl[114514],br[114514],bnum;
int val[114514];
int lazy[114514];
int maxb[114514],minb[114514];
inline void bld()
{
	size=sqrt(n)*log(n)/15;
	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;
	}
	br[bnum]=n;
	for(int i=1;i<=n;i++)
		val[i]=a[i];
	for(int i=1;i<=bnum;i++)
		sort(val+bl[i],val+br[i]+1);
}
inline int query(int l,int r,int k)
{
	if(belong[l]==belong[r])
	{
		int L=-1e9,R=1e9;
		int res=0;
		while(L<=R)
		{
			int mid=(L+R)/2;
			int cnt=0;
			for(int i=l;i<=r;i++)
				cnt+=(a[i]+lazy[belong[l]])<mid;
			if(cnt<k)
				L=mid+1,res=mid;
			else
				R=mid-1;
		}
		return res==1e9?-1:res;
	}
	int L=-1e9,R=1e9;
	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_bound(val+bl[i],val+br[i]+1,mid-lazy[i])-val-bl[i];
		if(cnt<k)
			L=mid+1,res=mid;
		else
			R=mid-1;
	}
	return res==1e9?-1:res;
}
inline 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];
		sort(val+bl[belong[l]],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];
	sort(val+bl[belong[l]],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];
	sort(val+bl[belong[r]],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)
			cout<<query(l,r,k)<<endl;
		else
			add(l,r,k);
	}
}
/*
10 1
114 514 1919 810 214 2187 123 324 435 125
1 4 5 114514 
*/