#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
#define int long long
int n,m;
const int N=1e6+520;
int tag[N],cl[N],cr[N],C[N],a[N];
//vector<int> v[N];
const int BLOCK=520;

int vsort[BLOCK][BLOCK];
int B_long[BLOCK];

char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
	int x=0,f=1;
	char ch=nc();
	while(ch<48||ch>57)
	{
		if(ch=='-')
			f=-1;
		ch=nc();
	}
	while(ch>=48&&ch<=57)
		x=x*10+ch-48,ch=nc();
	return x*f;
}
inline void write(int x)
{
	if(x<0)
		putchar('-'),x=-x;
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
	return;
}
inline int check(int l,int r,int x,int k){
	int cnt=0;
	if(tag[l]==tag[r]){
		if(vsort[tag[l]][1]+C[tag[l]]>x)	return 0;
		for(int i=l;i<=r;i++){
			if(a[i]+C[tag[i]]<=x)	cnt++;
		}
	}
	else{
		for(int i=l;i<=cr[l];i++){
			if(vsort[tag[i]][1]+C[tag[i]]>x)	break;
			if(a[i]+C[tag[i]]<=x)	cnt++;
		}
		for(int i=cl[r];i<=r;i++){
			if(vsort[tag[i]][1]+C[tag[i]]>x)	break;
			if(a[i]+C[tag[i]]<=x)	cnt++;
		}
		for(int i=tag[l]+1;i<=tag[r]-1;i++){
			int _l=1,_r=B_long[i],tmp=0;
			if(vsort[i][1]+C[i]>x)	continue;
			while(_l<=_r){
				int mid=(_l+_r)>>1;
				if(vsort[i][mid]+C[i]<=x){
					tmp=mid;
					_l=mid+1;
				}
				else{
					_r=mid-1;
				}
			}
			cnt+=tmp;
		}
	} 
	return cnt;
}
inline void build(){
	int B=BLOCK;
	for(int k=1;k<=(n%B==0?n/B:n/B+1);k++){
		for(int i=(k-1)*B+1;i<=min(k*B,n);i++){
			tag[i]=k;
			cl[i]=(k-1)*B+1;
			cr[i]=min(n,k*B);
			vsort[k][i-((k-1)*B+1)+1]=a[i];
			B_long[k]++;
		}
		sort(vsort[k]+1,vsort[k]+B_long[k]+1);
	}
	return ;
}
inline void add(int l,int r,int k){
	if(tag[l]==tag[r]){
		for(int i=l;i<=r;i++)	a[i]+=k;
		for(int i=cl[l];i<=cr[l];i++){
			vsort[tag[i]][i-cl[l]+1]=a[i];
		}
		sort(vsort[tag[l]]+1,vsort[tag[l]]+1+B_long[tag[l]]);
	}
	else{
		for(int i=l;i<=cr[l];i++){
			a[i]+=k;
		}
		for(int i=cl[l];i<=cr[l];i++){
			vsort[tag[l]][i-cl[l]+1]=a[i];
		}
		sort(vsort[tag[l]]+1,vsort[tag[l]]+1+B_long[tag[l]]);
		for(int i=cl[r];i<=r;i++){
			a[i]+=k;
		}
		for(int i=cl[r];i<=cr[r];i++){
			vsort[tag[r]][i-cl[r]+1]=a[i];
		}
		sort(vsort[tag[r]]+1,vsort[tag[r]]+1+B_long[tag[r]]);
		for(int i=tag[l]+1;i<=tag[r]-1;i++){
			C[i]+=k;
		}
	}
	return ;
}
inline void query(int l,int r,int k){
	int ans=0;
	if(r-l+1<k){
		write(-1);
		printf("\n");
		return ;
	}
	if(tag[l]==tag[r]){
		int minx=1e9,maxx=-1e9;
		for(int i=l;i<=r;i++){
			minx=min(a[i]+C[tag[i]],minx);
			maxx=max(a[i]+C[tag[i]],maxx);
		}
		while(minx<=maxx){
			int mid=(minx+maxx)>>1;
			if(check(l,r,mid,k)>=k){
				ans=mid;
				maxx=mid-1;
			}
			else{
				minx=mid+1;
			}
		}
	}
	else{
		int minx=1e9,maxx=-1e9;
		for(int i=l;i<=cr[l];i++){
			minx=min(a[i]+C[tag[i]],minx);
			maxx=max(a[i]+C[tag[i]],maxx);
		}
		for(int i=cl[r];i<=r;i++){
			minx=min(a[i]+C[tag[i]],minx);
			maxx=max(a[i]+C[tag[i]],maxx);
		}
		for(int i=tag[l]+1;i<=tag[r]-1;i++){
			minx=min(vsort[i][1]+C[i],minx);
			maxx=max(maxx,vsort[i][B_long[i]]+C[i]);
		}
		while(minx<=maxx){
			int mid=(minx+maxx)>>1;
			if(check(l,r,mid,k)>=k){
				ans=mid;
				maxx=mid-1;
			}
			else{
				minx=mid+1;
			}
		}
	}
	write(ans);
	printf("\n");
	return ;
}
signed main(){
	//freopen("Ynoi.in","r",stdin);
	//freopen("zhengjie.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++)	a[i]=read();
	build();
	for(int i=1;i<=m;i++){
		int opt=read(),l=read(),r=read(),k=read();
		if(opt&1){
			query(l,r,k);
		}
		else{
			add(l,r,k);
		}
	} 
	return 0;
}

$