我爱打扑克

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e5 + 10;
int n,m,a[MAXN],adde[MAXN];
inline int read(){
	int f = 1,res = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
	while(ch >= '0' && ch <= '9'){res = res * 10 + ch - '0';ch = getchar();}
	return res * f;
}
int blk[MAXN],L[MAXN],R[MAXN],cube,max_blk,v[MAXN];
inline void pushup(int pos){
	int lp = L[pos],rp = R[pos];
	for(int i = lp;i <= rp;i ++) v[i] = a[i];
	sort(v + L[pos],v + R[pos] + 1);
}
inline void modify_add(int l,int r,int k){
	int lpos = blk[l],rpos = blk[r];
	if(lpos == rpos){
		for(int i = l;i <= r;i ++) a[i] += k;
		pushup(lpos);
	}
	else{
		for(int i = lpos + 1;i <= rpos - 1;i ++) adde[i] += k;
		for(int i = l;i <= R[lpos];i ++) a[i] += k;
		pushup(lpos);
		for(int i = L[rpos];i <= r;i ++) a[i] += k;
		pushup(rpos);
	}
	return;
}
inline int max_(int l,int r){
	int lpos = blk[l],rpos = blk[r],ret = INT_MIN;
	if(lpos == rpos)
		for(int i = l;i <= r;i ++)
			ret = max(ret,a[i] + adde[blk[i]]);
	else{
		for(int i = lpos + 1;i <= rpos - 1;i ++)
			ret = max(ret,v[R[i]] + adde[i]);
		for(int i = l;i <= R[lpos];i ++)
			ret = max(ret,a[i] + adde[blk[i]]);
		for(int i = L[rpos];i <= r;i ++)
			ret = max(ret,a[i] + adde[blk[i]]);
	}
	return ret;
}
inline int min_(int l,int r){
	int lpos = blk[l],rpos = blk[r],ret = INT_MAX;
	if(lpos == rpos)
		for(int i = l;i <= r;i ++)
			ret = min(ret,a[i] + adde[blk[i]]);
	else{
		for(int i = lpos + 1;i <= rpos - 1;i ++)
			ret = min(ret,v[L[i]] + adde[i]);
		for(int i = l;i <= R[lpos];i ++)
			ret = min(ret,a[i] + adde[blk[i]]);
		for(int i = L[rpos];i <= r;i ++)
			ret = min(ret,a[i] + adde[blk[i]]);
	}
	return ret;
}
inline int check(int l,int r,int k){
	int lpos = blk[l],rpos = blk[r],ret = 0;
	if(lpos == rpos)
		for(int i = l;i <= r;i ++)
			if(a[i] + adde[lpos] <= k) ret ++;
	else{
		for(int i = l;i <= R[lpos];i ++)
			if(a[i] + adde[blk[i]] <= k) ret ++;
		for(int i = L[rpos];i <= r;i ++)
			if(a[i] + adde[blk[i]] <= k) ret ++;
		for(int i = lpos + 1;i <= rpos - 1;i ++){
			int lp = L[i],rp = R[i];
			if(v[L[i]] + adde[i] > k) continue;
			if(v[R[i]] + adde[i] <= k){
				ret += rp - lp + 1;
				continue;
			} 
			while(lp < rp){
				int Mid = (lp + rp) / 2 + 1;
				if(v[Mid] + adde[i] <= k) lp = Mid;
				else rp = Mid - 1;
			}
			if(v[lp] + adde[i] <= k) ret += lp - L[i] + 1;
		}
	}
	return ret;
}
inline int binary(int l,int r,int k){
	if(k < 1 || k > r - l + 1) return -1;
	int lp = min_(l,r),rp = max_(l,r),ret = -1;
	while(lp <= rp){
		int Mid = lp + rp >> 1;
		if(check(l,r,Mid) < k) 
			lp = Mid + 1;
		else{
			ret = Mid;
			rp = Mid - 1;
		}
	}
	return ret;
}
signed main(){
	n = read(),m = read();
	cube = sqrt(n);
	for(int i = 1;i <= n;i ++) a[i] = read();
	for(int i = 1;i <= n;i ++){
		blk[i] = (i - 1) / cube + 1;
		v[i] = a[i];
	}
	max_blk = blk[n];
	for(int i = 1;i <= max_blk;i ++)
		L[i] = (i - 1) * cube + 1,R[i] = i * cube;
	R[max_blk] = n;
	for(int i = 1;i <= max_blk;i ++)
		sort(v + L[i],v + R[i] + 1);
	while(m --){
		int opt,l,r,k;
		opt = read(),l = read(),r = read(),k = read();
		if(opt == 1)
			printf("%lld\n",binary(l,r,k));
		else
			modify_add(l,r,k);
	}
	return 0;
}