#include<bits/stdc++.h>
#define INF 1e9
using namespace std;
int n,m;
int block;
int bl[1145],tag[1145];
int v[214514];
vector<int>ver[1145];
int query(int x,int y,int k)
{
	int l = -INF,r = INF,ans;
	if (bl[x]==bl[y]){
		while (l <= r)
		{
			int mid = (l+r) >> 1;
			int sum = 0;
			for (int i = x; i <= y; i++)
				if (v[i]+tag[bl[i]] < mid) sum++;
			if (sum < k) l = mid+1,ans = mid;
			else r = mid-1;
		}
	}
	else
	{
		while (l <= r)
		{
			int mid = (l+r) >> 1;
			int sum = 0;
			for (int i = x; i <= bl[x]*block; i++)
				if (v[i]+tag[bl[i]] < mid) sum++;
			for (int i = (bl[y]-1)*block+1; i <= y; i++)
				if (v[i]+tag[bl[i]] < mid) sum++;
			for (int i = bl[x]+1; i <= bl[y]-1; i++)
				sum = sum+lower_bound(ver[i].begin(),ver[i].end(),mid-tag[i])-ver[i].begin();
			if (sum < k) l = mid+1,ans = mid;
			else r = mid-1;
		}	
	}
	return ans==INF?-1:ans;
}
void update(int l,int r,int k)
{
	if (bl[l]==bl[r])
	{
		for (int i = l; i <= r; i++)
			v[i] += k;
		ver[bl[l]].clear();
		for (int i = (bl[l]-1)*block+1; i <= bl[l]*block; i++)
			ver[bl[i]].push_back(v[i]);
		sort(ver[bl[l]].begin(),ver[bl[l]].end());
	}
	else
	{
		for (int i = l; i <= bl[l]*block; i++)
			v[i] += k;
		for (int i = (bl[r]-1)*block+1; i <= r; i++)
			v[i] += k;
		ver[bl[l]].clear(); ver[bl[r]].clear();
		for (int i = (bl[l]-1)*block+1; i <= bl[l]*block; i++)
			ver[bl[i]].push_back(v[i]);
		sort(ver[bl[l]].begin(),ver[bl[l]].end());
		for (int i = (bl[r]-1)*block+1; i <= bl[r]*block; i++)
			ver[bl[i]].push_back(v[i]);
		sort(ver[bl[r]].begin(),ver[bl[r]].end());
		for (int i = bl[l]+1; i <= bl[r]-1; i++)
			tag[i] += k;
	}
}
void build()
{
	block = sqrt(n);
    for (int i = 1; i <= n; i++){
    	bl[i] = (i-1)/block+1;
    	ver[bl[i]].push_back(v[i]);
	}
	for (int i = 1; i <= bl[n]; i++)
		sort(ver[i].begin(),ver[i].end());
}
int main()
{
    scanf("%d %d",&n,&m);
    for (int i = 1; i <= n; i++)
    	scanf("%d",&v[i]);
    build();
	while (m--)
	{
		int opt,l,r,k;
		scanf("%d%d%d%d",&opt,&l,&r,&k);
		if (opt==1){
			printf("%d\n",query(l,r,k));	
		}
		else update(l,r,k);
	}
    return 0;
}
/*
10 4
114 514 1919 810 214 2187 123 324 435 125
2 2 4 -453
1 1 3 2
1 1 3 1145
1 4 10 4
*/

自造数据全过