#include <bits/stdc++.h>

using namespace std;

const long long N = 1e5 + 5, M = 1e3 + 5;

long long n, m, ans, k,  L[M], R[M], cnt[N], tag[N], a[N], b[N], v[M][M], tot[M];

void D(long long x, long long y, long long o) {
	if (cnt[x] == cnt[y]) {
		tot[cnt[x]] = 0;
		for (long long i = x; i <= y; i++) {
			a[i] += o;
		}
		for (long long i = L[cnt[x]]; i <= R[cnt[x]]; i++) {
			v[cnt[x]][++tot[cnt[x]]] = a[i];
		}
		sort (v[cnt[x]] + 1, v[cnt[x]] + tot[cnt[x]] + 1);
		return;
	}
  tot[cnt[x]] = tot[cnt[y]] = 0;
	for (long long i = x; i <= R[cnt[x]]; i++) {
		a[i] += o;
	}
	for (long long i = cnt[x] + 1; i < cnt[y]; i++) {
		tag[i] += o;
	}
	for (long long i = L[cnt[y]]; i <= y; i++) {
		a[i] += o;
	}

  for (int i = L[cnt[x]]; i <= R[cnt[x]]; i++) {
    v[cnt[x]][++tot[cnt[x]]] = a[i];
  }
  for (int i = L[cnt[y]]; i <= R[cnt[y]]; i++) {
    v[cnt[y]][++tot[cnt[y]]] = a[i];
  }
  sort (v[cnt[x]] + 1, v[cnt[x]] + tot[cnt[x]] + 1);
  sort (v[cnt[y]] + 1, v[cnt[y]] + tot[cnt[y]] + 1);
	// long long i, j;
  // for (long long i = L[cnt[x]]; i <= R[cnt[x]]; i++) {
  //   b[i] = v[cnt[x]][i - L[cnt[x]] + 1];
  // }
  // for (long long i = L[cnt[y]]; i <= R[cnt[y]]; i++) {
  //   b[i] = v[cnt[y]][i - L[cnt[y]] + 1];
  // }
	// for (i = L[cnt[x]], j = x; i < x && j <= R[cnt[x]];) {
	//   if (b[i] < b[j]) {
  //     v[cnt[x]][++tot[cnt[x]]] = b[i++];
	// 	} else {
	// 		v[cnt[x]][++tot[cnt[x]]] = b[j++];
	// 	}
	// }
	// for (; i < x; v[cnt[x]][++tot[cnt[x]]] = b[i++]) {
	// }
	// for (; j <= R[cnt[x]]; v[cnt[x]][++tot[cnt[x]]] = b[j++]) {
	// }
	// for (i = L[cnt[y]], j = y; i < y && j <= R[cnt[y]];) {
	//   if (b[i] < b[j]) {
	//     v[cnt[y]][++tot[cnt[y]]] = b[i++];
	// 	} else {
	// 		v[cnt[y]][++tot[cnt[y]]] = b[j++];
	// 	}
	// }
	// for (; i < y; v[cnt[y]][++tot[cnt[y]]] = b[i++]) {
	// }
	// for (; j <= R[cnt[y]]; v[cnt[y]][++tot[cnt[y]]] =b[j++]) {
	// }
} 

void E(long long x, long long y, long long o) {
	if (cnt[x] == cnt[y]) {
		for (long long i = x; i <= y; i++) {
			ans += ((a[i] + tag[cnt[x]]) <= o);
		}
		return;
	}
	for (long long i = x; i <= R[cnt[x]]; i++) {
		ans += ((a[i] + tag[cnt[x]]) <= o);
	}
	for (long long i = cnt[x] + 1; i < cnt[y]; i++) {
		ans += upper_bound(v[i] + 1, v[i] + tot[i] + 1, o - tag[i]) - v[i] - 1;
	}
	for (long long i = L[cnt[y]]; i <= y; i++) {
		ans += ((a[i] + tag[cnt[y]]) <= o);
	}
}

long long F(long long x, long long y, long long c) {
	long long l = -2e9, r = 2e9;
	while (l <= r) {
		long long mid = (l + r) / 2ll;
		ans = 0;
		E(x, y, mid);
		if (ans < c) {
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	return l;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (long long i = 1; i <= n; i++) {
		cin >> a[i];
	}
	k = 350;
  int len = 0;
	for (long long i = 1; i <= n / k; i++) {
    len++;
		L[len] = R[len - 1] + 1, R[len] = i * k;
	}
	if (R[len] < n) {
		len++;
		L[len] = R[len - 1] + 1, R[len] = n;
	}
	for (long long i = 1; i <= len; i++) {
		for (long long j = L[i]; j <= R[i]; j++) {
      tot[i]++;
			v[i][tot[i]] = a[j];
			cnt[j] = i;
		}
		sort (v[i] + 1, v[i] + tot[i] + 1);
	}
	for (long long op, x, y, o; m--;) {
		cin >> op >> x >> y >> o;
		if (op == 2) {
			D(x, y, o);
		} else {
			if ((y - x + 1) < o) {
				cout << -1 << "\n";
				continue;
			} 
			cout << F(x, y, o) << "\n";
		}
	} 
	return 0;
}