T30pts

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define int long long
using namespace std;
const int SIZE=(1<<20)+1;
char buf[SIZE],*p1=buf,*p2=buf;
char buffer[SIZE];
int op1=-1;
const int op2=SIZE-1;
inline char readchar() {
	if(p1!=p2) {
		return *p1++;
	}
	return p1==(p2=(p1=buf)+fread(buf,1,SIZE-1,stdin))?EOF:*p1++;
}
inline void flush() {
	fwrite(buffer,1,op1+1,stdout),op1=-1;
}
inline void writechar(const char &x) {
	if(op1==op2) flush();
	buffer[++op1]=x;
}
inline int read() {
	int s=1,c=readchar(),x=0;
	while(c<=32) {
		c=readchar();
	}
	if(c=='-') {
		s=-1,c=readchar();
	}
	for(; ('0'<=c && c<='9'); c=readchar()) {
		x=x*10+c-'0';
	}
	return x*s;
}
inline void write(int x) {
	if(x<0) {
		writechar('-'),x=-x;
	}
	char s[25];
	int n=0;
	while(x || !n) {
		s[n++]='0'+x%10,x/=10;
	}
	while(n--) {
		writechar(s[n]);
	}
} 
const int N=1e5+5,M=1e3+5;
int k;
int n,m;
int id[N];
int a[N],tag[N];
int ku[M][M];
int sm[N];
int i,lid,rid,mid;
int op,l,r,l1,r1,cnt,qwq;
int tot[N];
inline bool check(){
	cnt=upper_bound(tot,tot+qwq,mid)-tot;
	for (i=lid+1;i<rid;++i){
		cnt+=upper_bound(ku[i],ku[i]+sm[i],mid-tag[i])-ku[i];
//		cout<<i<<" "<<upper_bound(ku[i].begin(),ku[i].end(),mid-tag[i])-ku[i].begin()<<endl;
	}
//	cout<<cnt<<endl;
	return cnt>=k;
}
signed main(){
	n=read(),m=read();
	k=sqrt(n);
	for (int i=1;i<=n;++i) id[i]=i/k;
	for (int i=1;i<=n;++i) a[i]=read(),ku[id[i]][sm[id[i]]]=a[i],++sm[id[i]];
//	for (int i=1;i<=n;++i) cout<<id[i]<<" ";
//	cout<<endl;
	k=0;
	while (sm[k]!=0) sort(ku[k],ku[k]+sm[k]),++k;
	for (int _=0;_<m;++_){
		op=read(),l=read(),r=read(),k=read();
		lid=id[l],rid=id[r];
		if (op==1){//查询
			l1=-5e9,r1=25e9,mid;//二分
			if (r-l+1<k){write(-1);writechar('\n');continue;}
			if (lid==rid || lid+1==rid){//特判，时间复杂度sqrt(n)
				for (i=l;i<=r;++i) tot[i-l]=a[i]+tag[id[i]];
				sort(tot,tot+(r-l+1));
				write(tot[k-1]);
				writechar('\n');
				continue;
			}
			qwq=0;
			for (i=l;id[i]==lid;++i,++qwq) tot[qwq]=a[i]+tag[lid];
			for (i=r;id[i]==rid;--i,++qwq) tot[qwq]=a[i]+tag[rid];
			sort(tot,tot+qwq);
			while (l1<r1){//值域二分
				mid=(l1+r1)/2;
				if (check()) r1=mid;
				else l1=mid+1;
			}
			write(l1);
			writechar('\n');
		}else{
			if (lid==rid){//特殊处理
				for (i=l;i<=r;++i) a[i]+=k;
				sm[lid]=0;
				l1=l;
				while (id[l1]==lid && l1>=1) --l1;
				++l1;
				while (id[l1]==lid && l1<=n) ku[lid][sm[lid]]=a[l1],++sm[lid],++l1;
				sort(ku[lid],ku[lid]+sm[lid]);
				continue;
			}
//			ku[lid].clear(),ku[rid].clear();
			sm[lid]=sm[rid]=0;
			l1=l;
			for (;id[l1]==lid;++l1) a[l1]+=k;
			--l1;
			for (;id[l1]==lid;--l1) ku[lid][sm[lid]]=a[l1],++sm[lid];
			r1=r;
			for (;id[r1]==rid;--r1) a[r1]+=k;
			++r1;
			for (;id[r1]==rid;++r1) ku[rid][sm[rid]]=a[r1],++sm[rid];
			sort(ku[lid],ku[lid]+sm[lid]);sort(ku[rid],ku[rid]+sm[rid]);
			for (i=lid+1;i<rid;++i) tag[i]+=k;
		}
	}
	flush();
	return 0;
}
/*
10 2
962 458 -441 -239 839 310 -747 -164 -330 -296 
2 7 7 986
1 2 9 7
*/
//10 1
//962 458 -441 -239 839 310 -747 -164 -330 -296 
//1 2 9 7