#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000005;
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;
}
int op,n,q,bl,tot,l,r,k;
int a[N],b[N],id[N],tag[1005],L[1005],R[1005]; 
inline void init (){
	in (n);in (q);
	bl=(int) (sqrt (n));
	int tot=(int) (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);
}
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;i<=r;++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;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;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];++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];++i){
		int pos=lower_bound (b+L[i],b+R[i]+1,key-tag[i])-b-L[i];
		sum+=pos;
	}
	return sum<K;
}
inline int query (int l,int r,int k){
	if (k<1||k>r-l+1) return -1;
	int ll=-(2e9),rr=2e9;
	while (ll<rr){
		int mid=ll+rr>>1;
		if (check (mid,l,r,k)) ll=mid+1;
		else rr=mid;
	}
	return ll-1;
}
inline void solve (){
	for (int i=1;i<=q;++i){
		in (op);in (l);in (r);in (k); 
		if (op==1) printf ("%d\n",query (l,r,k));
		if (op==2) update (l,r,k);
	}
}
signed main(){
	init ();
	solve ();
	return 0;
}
/*
10 10
15 11 -18 12 6 9 14 -2 -10 6  
1 2 3 1
2 2 4 -3
1 4 10 7
1 2 2 1
1 8 8 1
2 4 10 4
1 4 10 1
1 7 10 4
2 1 4 -5
1 1 8 4

-18
14
8
-2
6
18
8
*/

加注释的是补充的样例，也过了，交上去就是0分。

大概是query或者check的问题