#include<bits/stdc++.h>
using namespace std;
#define ONLINE_JUDGE
namespace Fread {
	const int SIZE = 1 << 21;
	char buf[SIZE], *S, *T;
	inline char getchar() {
		if (S == T) {
			T = (S = buf) + fread(buf, 1, SIZE, stdin);
			if (S == T) return '\n';
		}
		return *S++;
	}
}
using namespace Fread;
namespace Fwrite {
	const int SIZE = 1 << 21;
	char buf[SIZE], *S = buf, *T = buf + SIZE;
	inline void flush() {
		fwrite(buf, 1, S - buf, stdout);
		S = buf;
	}
	inline void putchar(char c) {
		*S++ = c;
		if (S == T) flush();
	}
	struct NTR {
		~NTR() {
			flush();
		}
	} ztr;
}
using namespace Fwrite;
#define getchar Fread::getchar
#define putchar Fwrite::putchar
namespace Fastio {
	struct Reader {
		template <typename T> Reader& operator >> (T &x) {
			x = 0;
			short f = 1;
			char c = getchar();
			while (c < '0' || c > '9') {
				if (c == '-') f *= -1;
				c = getchar();
			}
			while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
			x *= f;
			return *this;
		}
		Reader() {}
	} cin;
	const char endl = '\n';
	struct Writer {
		const int Setprecision = 6;
		typedef int mxdouble;
		template <typename T> Writer& operator << (T x) {
			if (x == 0) {
				putchar('0');
				return *this;
			}
			if (x < 0) putchar('-'), x = -x;
			static short sta[40];
			short top = 0;
			while (x > 0) sta[++top] = x % 10, x /= 10;
			while (top > 0) putchar(sta[top] + '0'), top--;
			return *this;
		}
		Writer() {}
	} cout;
}
using namespace Fastio;
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
struct nd {
	int l,r;
	long long flag;
} c[405];
short pos[100005];
long long a[100005],minn,maxx;
bool cmp(int x,int y) {
	return a[x]<a[y];
}
int b[100005],n,m;
const int cnt[]= {1,2,4,8,16,32,64,128,256,512};
void add(int l,int r,int k) {
	for(int i=l; i<=r; ++i) {
		if(c[pos[i]].l==i&&c[pos[i]].r<=r) {
			c[pos[i]].flag+=k;
			i=c[pos[i]].r;
		} else {
			a[i]+=k;
		}
	}
	if(c[pos[l]].l^l) stable_sort(b+c[pos[l]].l,b+c[pos[l]].r+1,cmp);
	if(c[pos[r]].r^r) stable_sort(b+c[pos[r]].l,b+c[pos[r]].r+1,cmp);
}
void check(int l,int r) {
	minn=10000000000,maxx=0;
	for(int i=l; i<=r; ++i) {
		if(c[pos[i]].l==i&&c[pos[i]].r<=r) {
			minn=min(minn,a[b[c[pos[i]].l]]+c[pos[i]].flag);
			maxx=max(maxx,a[b[c[pos[i]].r]]+c[pos[i]].flag);
			i=c[pos[i]].r;
		} else {
			minn=min(minn,a[i]+c[pos[i]].flag);
			maxx=max(maxx,a[i]+c[pos[i]].flag);
		}
	}
}
int ask(int l,int r,long long k) {
	int sum=0;
	for(int i=l; i<=r; ++i) {
		if(c[pos[i]].l==i&&c[pos[i]].r<=r) {
			if(a[b[c[pos[i]].l]]+c[pos[i]].flag>k) {
				i=c[pos[i]].r;
				continue;
			} else if(a[b[c[pos[i]].r]]+c[pos[i]].flag<=k) {
				sum+=c[pos[i]].r-c[pos[i]].l+1;
				i=c[pos[i]].r;
				continue;
			}
			int it=0;
			for(int j=8; ~j; j--) {
				if(c[pos[i]].l+it+cnt[j]>c[pos[i]].r) continue;
				if(a[b[c[pos[i]].l+it+cnt[j]]]+c[pos[i]].flag<=k) it+=cnt[j];
			}
			sum+=it+1;
			i=c[pos[i]].r;
		} else {
			if(a[i]+c[pos[i]].flag<=k) sum++;
		}
	}
	return sum;
}
int main() {
	cin>>n>>m;
	const short len=sqrt(n*2);
	for(int i=1; i<=n; ++i) {
		cin>>a[i];
		a[i]+=2000000000;
		pos[i]=i/len+(i%len!=0);
		c[pos[i]].r=i;
		if(c[pos[i]].l==0) c[pos[i]].l=i;
	}
	for(int i=1; i<=n; ++i) b[i]=i;
	for(int i=1; i<=pos[n]; ++i) stable_sort(b+c[i].l,b+c[i].r+1,cmp);
	int k;
	short op;
	for(int i=1,l,r; i<=m; ++i) {
		cin>>op>>l>>r>>k;
		if(op==2) add(l,r,k);
		else {
			if(k>r-l+1) {
				putchar('-'),putchar('1'),putchar('\n');
				continue;
			}
			check(l,r);
			long long L=minn,R=maxx,ans=10000000000;
			if(k==1) {
				cout<<minn-2000000000;
				putchar('\n');
				continue;
			} else if(k==r-l+1) {
				cout<<maxx-2000000000;
				putchar('\n');
				continue;
			}
			while(L<=R) {
				long long mid=(L+R)>>1;
				if(mid>=ans) {
					R=mid-1;
					continue;
				}
				if(ask(l,r,mid)>=k) {
					R=mid-1;
					ans=min(ans,mid);
				} else {
					L=mid+1;
				}
			}
			cout<<ans-2000000000;
			putchar('\n');
		}
	}
	return 0;
}