rt

#include<bits/stdc++.h>
using namespace std;
struct kuai {
	int mxx=INT_MIN;
	int mnn=INT_MAX;
	int l;
	int r;
};
int meikuai,a,b;
kuai block[1000005];
int c[1000005],pai[1000005],lan[1000005],e[1000005];
int getkuai(int x) {
	return (x-1)/meikuai+1;
}
int main() {
	//freopen("1.out","r",stdin);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>a>>b;
	for(int i=1; i<=a; i++) {
		cin>>c[i];
		pai[i]=c[i];
	}
	meikuai=(int)sqrt(a);
	int mx=INT_MIN,mn=INT_MAX,cnt=1;
	for(int i=1; i<=a; i++) {
		mx=max(c[i],mx);
		mn=min(c[i],mn);
		if(i%meikuai==0) {
			block[cnt].mxx=mx;
			block[cnt].mnn=mn;
			block[cnt].l=block[cnt-1].r+1;
			block[cnt].r=i;
			sort(pai+block[cnt].l,pai+block[cnt].r+1);
			mx=INT_MIN;
			mn=INT_MAX;
			cnt++;
		}
	}
	if(a%(int)sqrt(a)!=0) {
		block[cnt].mxx=mx;
		block[cnt].mnn=mn;
		block[cnt].l=block[cnt-1].r+1;
		block[cnt].r=a;
	}
	char ji;
	int quel,quer,lid,rid,d,sum=0;
	for(int i=0; i<b; i++) {
		cin>>ji;
		cin>>quel>>quer;
		cin>>d;
		lid=getkuai(quel);
		rid=getkuai(quer);
		if(ji=='2') {
			if(lid==rid) {
				for(int n=quel; n<=quer; n++) {
					c[n]+=d;
					pai[n]=c[n];
				}
				block[lid].mxx=INT_MIN;
				block[lid].mnn=INT_MAX;
				for(int n=block[lid].l; n<=block[lid].r; n++) {
					block[lid].mxx=max(block[lid].mxx,c[n]+lan[lid]);
					block[lid].mnn=min(block[lid].mnn,c[n]+lan[lid]);
				}
				if(!is_sorted(pai+block[lid].l,pai+block[lid].r+1)) sort(pai+block[lid].l,pai+block[lid].r+1);
			} else {
				for(int n=quel; n<=block[lid].r; n++) {
					c[n]+=d;
				}
				block[lid].mxx=INT_MIN;
				block[lid].mnn=INT_MAX;
				for(int n=block[lid].l; n<=block[lid].r; n++) {
					block[lid].mxx=max(block[lid].mxx,c[n]+lan[lid]);
					block[lid].mnn=min(block[lid].mnn,c[n]+lan[lid]);
				}
				for(int n=block[lid].l; n<=block[lid].r; n++) {
					pai[n]=c[n];
				}
				if(!is_sorted(pai+block[lid].l,pai+block[lid].r+1)) sort(pai+block[lid].l,pai+block[lid].r+1);
				for(int n=lid+1; n<rid; n++) {
					block[n].mxx+=d;
					block[n].mnn+=d;
					lan[n]+=d;
				}
				for(int n=block[rid].l; n<=quer; n++) {
					c[n]+=d;
				}
				block[rid].mxx=INT_MIN;
				block[rid].mnn=INT_MAX;
				for(int n=block[rid].l; n<=block[rid].r; n++) {
					block[rid].mxx=max(block[rid].mxx,c[n]+lan[rid]);
					block[rid].mnn=min(block[rid].mnn,c[n]+lan[rid]);
				}
				for(int n=block[rid].l; n<=block[rid].r; n++) {
					pai[n]=c[n];
				}
				if(!is_sorted(pai+block[rid].l,pai+block[rid].r+1)) sort(pai+block[rid].l,pai+block[rid].r+1);
			}
		} else {
			if(quel+d-1>quer||d<1){
				cout<<-1<<'\n';
				continue;
			}
			if(lid==rid) {
				for(int n=quel; n<=quer; n++) {
					e[n]=c[n];
				}
				sort(e+quel,e+quer+1);
				cout<<e[quel+d-1]<<'\n';
			} else {
				sum=0;
				mx=INT_MIN;
				mn=INT_MAX;
				for(int n=quel; n<=block[lid].r; n++) {
					mx=max(c[n]+lan[lid],mx);
					mn=min(c[n]+lan[lid],mn);
				}
				for(int n=lid+1; n<rid; n++) {
					mx=max(block[n].mxx,mx);
					mn=min(block[n].mnn,mn);
				}
				for(int n=block[rid].l; n<=quer; n++) {
					mx=max(c[n]+lan[rid],mx);
					mn=min(c[n]+lan[rid],mn);
				}
				if(d==1){
					cout<<mn<<'\n';
					continue;
				}
				if(d==quer-quel+1){
					cout<<mx<<'\n';
					continue;
				}
				long long mid=(mx+mn)/2;
				while(sum!=d) {
					mx=INT_MIN;
					mn=INT_MAX;
					for(int n=quel; n<=block[lid].r; n++) {
						mx=max(c[n]+lan[lid],mx);
						mn=min(c[n]+lan[lid],mn);
					}
					for(int n=lid+1; n<rid; n++) {
						mx=max(block[n].mxx,mx);
						mn=min(block[n].mnn,mn);
					}
					for(int n=block[rid].l; n<=quer; n++) {
						mx=max(c[n]+lan[rid],mx);
						mn=min(c[n]+lan[rid],mn);
					}
					sum=0;
					for(int n=quel; n<=block[lid].r; n++) {
						if(mid>=c[n]+lan[lid]) sum++;
					}
					for(int n=lid+1; n<rid; n++) {
						if(block[n].mnn>=mid) sum+=block[n].r-block[n].l+1;
						else if(block[n].mxx<mid) continue;
						else sum+=(upper_bound(pai+block[n].l,pai+block[n].r+1,d-lan[n])-pai)-block[n].l;
					}
					for(int n=block[rid].l; n<=quer; n++) {
						if(mid>=c[n]+lan[rid]) sum++;
					}
					if(sum>d) {
						mid=((mn+mid)>>1)+1;
					} else if(sum<d) {
						mid=((mx+mid)>>1)+1;
					}
				}
				cout<<mid<<'\n';
			}
		}
	}
	return 0;
}