WA ( 0pts )

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10;
int n, m;
int st[N], ed[N], add[N], pos[N];
int a[N], d[N];
int block, num;

inline int read()
{
	int x = 0, f = 0; char ch = getchar();
	while (!isdigit(ch)) f ^= !(ch ^ 45), ch = getchar();
	while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

void build()
{
	block = sqrt(n), num = (n - 1) / block + 1;
	for (int i = 1; i <= n; i ++ ) pos[i] = (i - 1) / block + 1;
	for (int i = 1; i <= num; i ++ )
		st[i] = (i - 1) * block + 1, ed[i] = i * block;
	ed[num] = n;
	for (int i = 1; i <= num; i ++ )
		sort(d + st[i], d + ed[i] + 1);
}

void update(int l, int r, int k)
{
	int x = pos[l], y = pos[r];
	if (x == y)
	{
		for (int i = l; i <= r; i ++ ) a[i] += k;
		for (int i = st[x]; i <= ed[x]; i ++ ) d[i] = a[i];
		sort(d + st[x], d + ed[x] + 1);
		return;
	}
	for (int i = l; i <= ed[x]; i ++ ) a[i] += k;
	for (int i = st[x]; i <= ed[x]; i ++ ) d[i] = a[i];
	sort(d + st[x], d + ed[x] + 1);
	for (int i = st[y]; i <= r; i ++ ) a[i] += k;
	for (int i = st[y]; i <= ed[y]; i ++ ) d[i] = a[i];
	sort(d + st[y], d + ed[y] + 1);
	for (int i = x + 1; i < y; i ++ ) add[i] += k;
}
int check(int l, int r, int k)
{
	int x = pos[l], y = pos[r];
	if (x == y)
	{
		int res = 0;
		for (int i = l; i <= r; i ++ ) res += (a[i] + add[x] <= k);
		return res;
	}
	int res = 0;
	for (int i = l; i <= ed[x]; i ++ ) res += (a[i] + add[x] <= k);
	for (int i = st[y]; i <= r; i ++ ) res += (a[i] + add[y] <= k);
	for (int i = x + 1; i < y; i ++ )
	{
		if (d[st[i]] + add[i] > k) continue;
		if (d[ed[i]] + add[i] <= k)
		{
			res += ed[i] - st[i] + 1;
			continue;
		}
		int L = st[i], R = ed[i], pos;
		while (L <= R)
		{
			int mid = L + R >> 1;
			if (d[mid] + add[i] <= k) L = mid + 1, pos = mid;
			else R = mid - 1;
		}
		if (d[pos] + add[i] <= k) res += pos - st[i] + 1;
	}
	return res;
}
int queryMax(int l, int r)
{
	int x = pos[l], y = pos[r];
	int res = INT_MIN;
	if (x == y)
	{
		for (int i = l; i <= r; i ++ ) res = max(res, a[i] + add[x]);
		return res;
	}
	for (int i = l; i <= ed[x]; i ++ ) res = max(res, a[i] + add[x]);
	for (int i = st[y]; i <= r; i ++ ) res = max(res, a[i] + add[y]);
	for (int i = x + 1; i < y; i ++ ) res = max(res, d[ed[i]] + add[i]);
	return res;
}
int queryMin(int l, int r)
{
	int x = pos[l], y = pos[r];
	int res = INT_MAX;
	if (x == y)
	{
		for (int i = l; i <= r; i ++ ) res = min(res, a[i] + add[x]);
		return res;
	}
	for (int i = l; i <= ed[x]; i ++ ) res = min(res, a[i] + add[x]);
	for (int i = st[y]; i <= r; i ++ ) res = min(res, a[i] + add[y]);
	for (int i = x + 1; i < y; i ++ ) res = min(res, d[ed[i]] + add[i]);
	return res;
}
int query(int l, int r, int k)
{
	if (k < 1 || k > r - l + 1) return -1;
	int x = pos[l], y = pos[r];
	int res = -1;
	int L = queryMin(l, r), R = queryMax(l, r);
	while (L <= R)
	{
		int mid = L + R >> 1;
		if (check(l, r, mid) < k) L = mid + 1;
		else res = mid, R = mid - 1;
	}
	return res;
}

signed main()
{
	n = read(), m = read();
	for (int i = 1; i <= n; i ++ ) a[i] = read(), d[i] = a[i];
	build();
	while (m -- )
	{
		int p = read(), l = read(), r = read(), k = read();
		if (p == 1)
			printf("%lld\n", query(l, r, k));
		if (p == 2)
			update(l, r, k);
	}
	return 0;
}