#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
inline void in (int &x){
	int f=1;x=0;char c=getchar();
	while (c>'9'||c<'0'){if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	x*=f;
}
inline void out (int x){
	char F[20];int tmp=x>0?x:-x,cnt=0;
	if (x<0) putchar('-');
	while (tmp){F[cnt++]=tmp%10+'0';tmp/=10;}
	while (cnt>0) putchar(F[--cnt]);puts ("");
}
int op,n,q,bl=175,tot,l,r,k;
int a[N],b[N],id[N],tag[1005],L[1005],R[1005]; 
inline int Min (int l,int r){
	int minn=2147483647;
	if (id[l]==id[r]){
		for (int i=l;i<=r;++i)
			minn=minn>a[i]+tag[id[i]]?a[i]+tag[id[i]]:minn;
		return minn;
	}
	for (int i=l;i<=R[id[l]];++i)
		minn=minn>a[i]+tag[id[l]]?a[i]+tag[id[l]]:minn;
	for (int i=r;i>=L[id[r]];--i)
		minn=minn>a[i]+tag[id[r]]?a[i]+tag[id[r]]:minn;
	for (int i=id[l]+1;i<=id[r]-1;++i)
		minn=minn>b[L[i]]+tag[i]?b[L[i]]+tag[i]:minn;
	return minn;
} 
inline int Max (int l,int r){
	int maxx=-2147483647;
	if (id[l]==id[r]){
		for (int i=l;i<=r;++i)
			maxx=maxx<a[i]+tag[id[i]]?a[i]+tag[id[i]]:maxx;
		return maxx;
	}
	for (int i=l;i<=R[id[l]];++i)
		maxx=maxx<a[i]+tag[id[l]]?a[i]+tag[id[l]]:maxx;
	for (int i=r;i>=L[id[r]];--i)
		maxx=maxx<a[i]+tag[id[r]]?a[i]+tag[id[r]]:maxx;
	for (int i=id[l]+1;i<=id[r]-1;++i)
		maxx=maxx<b[R[i]]+tag[i]?b[R[i]]+tag[i]:maxx;
	return maxx;
} 
inline void update (int l,int r,int k){
	if (id[l]==id[r]){
		for (int i=l;i<=r;++i) a[i]+=k;
		for (int i=L[id[l]];i<=R[id[l]];++i) b[i]=a[i];
		sort (b+L[id[l]],b+R[id[r]]+1);
		return ;
	}
	for (int i=l;i<=R[id[l]];++i) a[i]+=k;
	for (int i=L[id[l]];i<=R[id[l]];++i) b[i]=a[i];
	sort (b+L[id[l]],b+R[id[l]]+1);
	for (int i=r;i>=L[id[r]];--i) a[i]+=k;
	for (int i=R[id[r]];i>=L[id[r]];--i) b[i]=a[i];
	sort (b+L[id[r]],b+R[id[r]]+1);
	for (int i=id[l]+1;i<=id[r]-1;++i) tag[i]+=k;
} 
inline bool check (int key,int l,int r,int K){
	int sum=0;
	if (id[l]==id[r]){
		for (int i=l;i<=r;++i)
			sum+=(tag[id[i]]+a[i])<=key;
		return sum<K;
	}
	for (int i=l;i<=R[id[l]];++i) sum+=(tag[id[l]]+a[i])<=key; 
	for (int i=r;i>=L[id[r]];--i) sum+=(tag[id[r]]+a[i])<=key;
	for (int i=id[l]+1;i<=id[r]-1;++i){
		if (b[L[i]]+tag[i]>key) continue;
		if (b[R[i]]+tag[i]<=key){sum+=R[i]-L[i]+1;continue ;}
		int ll=L[i],rr=R[i];
		while (ll<rr){
			int mid=ll+rr+1>>1;
			if (b[mid]+tag[i]<=key) ll=mid;
			else rr=mid-1;
		}
		if (b[ll]+tag[i]<=key) sum+=ll-L[i]+1;
	}
	return sum<K;
}
inline int query (int l,int r,int k){
	if (k<1||k>r-l+1) return -1;
	int ans=-1,ll=Min (l,r),rr=Max (l,r);
	if (k==1) return ll;if (k==r-l+1) return rr;
	while (ll<rr){
		int mid=ll+rr>>1;
		if (check (mid,l,r,k)) ll=mid+1;
		else rr=mid;
	}
	return ll;
}
signed main(){
	in (n);in (q);
	tot=n/bl+(n%bl!=0); 
	for (int i=1;i<=n;++i){
		in (a[i]);b[i]=a[i];
	}
	for (int i=1;i<=n;++i)
		id[i]=(i-1)/bl+1;
	for (int i=1;i<=tot;++i){
		L[i]=(i-1)*bl+1;R[i]=i*bl; 
	}
	R[tot]=n; 
	for (int i=1;i<=tot;++i)
		sort (b+L[i],b+R[i]+1);
	for (int i=1;i<=q;++i){
		in (op);in (l);in (r);in (k); 
		if (op==1) out (query (l,r,k));
		else update (l,r,k);
	}
	return 0;
}