#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 500005;
#define rg register

static char buf[1000000],*p1=buf,*p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
inline int read(){int x=0,f=1;char c=getchar();while(c<'0' || c>'9'){if(c=='-') f=-1;c=getchar();}while(c>='0' && c<='9') {x=x*10+c-48;c=getchar();}return x*f;}
inline void write(int x){static char buf[20];static int len=-1;if(x<0)putchar('-'),x=-x;do buf[++len]=x%10,x/=10;while(x);while(len>=0)putchar(buf[len--]+'0');}

int a[MAX];
int b[MAX];
int id[MAX]; 
int pls[MAX];

int L[MAX], R[MAX];

inline void add(int l, int r, int c){
	int p = id[l], q = id[r];
	if(p == q){
		for(rg int i = l; i <= r; i++)	b[i] += c;
		for(rg int i = L[p]; i <= R[p]; i++){
			a[i] = b[i];
		}
		sort(a+L[p], a+R[p]+1);
	}else{
		for(rg int i = p+1; i <= q-1; i++)	pls[i] += c;
		for(rg int i = l; i <= R[p]; i++)	b[i] += c;
		for(rg int i = L[p]; i <= R[p]; i++)	a[i] = b[i];
		sort(a+L[p], a+R[p]+1);
		for(rg int i = r; i >= L[q]; i--)	b[i] += c;
		for(rg int i = L[q]; i <= R[q]; i++)	a[i] = b[i];
		sort(a+L[q], a+R[q]+1);
	}
}

inline int query(int l, int r, int c){
	int p = id[l], q = id[r];
	if(p == q){
		int ans = 0;
		if(a[R[p]] + pls[p] <= c)	ans += r-l+1;
		else if(a[L[p]] + pls[p] <= c)	for(int i = l; i <= r; i++)	if(b[i] + pls[p] <= c)	ans++;
		return ans;
	}else{
		int ans = 0;
		for(rg int i = p+1; i <= q-1; i++){
			if(a[R[i]] + pls[i] <= c)	ans += R[i] - L[i] + 1;
			else if(a[L[i]] + pls[i] <= c){
				int x1 = upper_bound(a+L[i], a+R[i]+1, c-pls[i]) - a - L[i];
				ans += x1;
			}
		}
		if(a[R[p]] + pls[p] <= c)	ans += R[p]-l+1;
		else if(a[L[p]] + pls[p] <= c)  for(int i = l; i <= R[p]; i++)	if(b[i] + pls[p] <= c)	ans++;
		if(a[R[q]] + pls[q] <= c)	ans += r - L[q] + 1;
		else if(a[L[q]] + pls[q] <= c)	for(int i = L[q]; i <= r; i++)	if(b[i] + pls[q] <= c)	ans++;
		return ans;
	}
}

inline int getmax(int l, int r){
	int p = id[l], q = id[r];
	int ans = -0x3f3f3f3f;
	if(p == q){
		for(rg int i = l; i <= r; i++)	ans = max(ans, b[i]+pls[p]);
	}else{
		for(rg int i = p+1; i <= q-1; i++)	ans = max(ans, a[R[i]]+pls[i]);
		for(rg int i = l; i <= R[p]; i++)	ans = max(ans, b[i]+pls[p]);
		for(rg int i = L[q]; i <= r; i++)	ans = max(ans, b[i]+pls[q]);
	}
	return ans;
}

inline int getmin(int l, int r){
	int p = id[l], q = id[r];
	int ans = 0x3f3f3f3f;
	if(p == q){
		for(rg int i = l; i <= r; i++)	ans = min(ans, b[i]+pls[p]);
	}else{
		for(rg int i = p+1; i <= q-1; i++)	ans = min(ans, a[L[i]]+pls[i]);
		for(rg int i = l; i <= R[p]; i++)	ans = min(ans, b[i]+pls[p]);
		for(rg int i = L[q]; i <= r; i++)	ans = min(ans, b[i]+pls[q]);
	}
	return ans;
}

inline int ask(int dl, int dr, int k){
	if(dr-dl+1 < k or k < 1)	return -1;
	int l = getmin(dl, dr), r = getmax(dl, dr);
	if(id[dl] == id[dr]){
		int c[dr-dl+1];
		for(int i = 0; i <= dr - dl; i++){
			c[i] = b[i+dl];
		}
		sort(c, c+dr-dl+1);
		return c[k-1]+pls[id[dl]];
	}
	int ans = 0;
	while(l <= r){
		int mid = (l+r)>>1;
		int check = query(dl, dr, mid);
		if(check < k)	l = mid+1;
		else r = mid-1, ans = mid;
	}
	return ans;
}

signed main(){
	int n = read(), m = read();
	for(rg int i = 1; i <= n; i++)	a[i] = read(), b[i] = a[i];
	int t = sqrt(n);
	for(rg int i = 1; i <= t; i++)	L[i] = (i-1) * t+1, R[i] = i * t;
	if(R[t] < n)	t++, L[t] = R[t-1]+1, R[t] = n;
	for(rg int i = 1; i <= t; i++){
		for(rg int j = L[i]; j <= R[i]; j++){
			id[j] = i;
		}
	} // 块预处理
	for(rg int i = 1; i <= t; i++){
		sort(a+L[i], a+R[i]+1);
	}
	for(rg int i = 1; i <= m; i++){
		int op = read(), l = read(), r = read(), k = read();
		if(op == 1) write(ask(l, r, k)), putchar('\n');
		else add(l, r, k);
	}
	return 0;
}