#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm> 
using namespace std;
const int Max=100005;
const int INF=0x3f3f3f; 
const int block=400;
const int N=Max/block+5;
int B;
int bl[N],br[N],bw[Max],lx[N];
int a[Max],t1,t2,t3;
struct node{
	int z;
	int p;
};
node b[Max],c1[Max],c2[Max];
bool cmp(node x,node y){
	return x.z<y.z;
}
int ansl[N],ansr[N],anss[N];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	B=(n-1)/block+1;
	for(int i=1;i<=B;i++){
		bl[i]=br[i-1]+1;
		br[i]=br[i-1]+block;
	} 
	br[B]=n;
	for(int i=1;i<=B;i++){
		for(int j=bl[i];j<=br[i];j++){
			bw[j]=i;
			b[b[j].p=j].z=a[j];
		}
		stable_sort(b+bl[i],b+br[i]+1,cmp);
	}
	while(m--){
		int opt,l,r,k;
		scanf("%d%d%d%d",&opt,&l,&r,&k);
		int ll=bw[l],rr=bw[r];
		if(opt==1){
			if(k>(r-l+1)){
				cout<<-1<<endl;
				continue;
			}
			int L=-2000000000,R=2000000000,ans=0;
			for(int i=ll;i<=rr;i++){
				L=min(L,b[bl[i]].z+lx[i]);
				R=max(R,b[br[i]].z+lx[i]);
				ansl[i]=bl[i];
				ansr[i]=br[i];
				anss[i]=bl[i]-1;
			}	
			while(L<=R){
				int md=(L+R)/2;
				int s=0;
				if(ll==rr){
					for(int i=l;i<=r;i++){
						if(a[i]+lx[ll]<=md){
							s++;
						}
					}
				}
				else{
					for(int i=l;i<=br[ll];i++){
						if(a[i]+lx[ll]<=md){
							s++;
						}
					}
					for(int i=bl[rr];i<=r;i++){
						if(a[i]+lx[rr]<=md){
							s++;
						}
					}
					for(int i=ll+1;i<rr;i++){
						int fl=ansl[i];
						int fr=ansr[i];
						anss[i]=bl[i]-1;
						while(fl<=fr){
							int fmd=fl+fr>>1;
							if(b[fmd].z+lx[i]<=md){
								anss[i]=fmd;
								fl=fmd+1;
							}
							else{
								fr=fmd-1;
							}
						}
						s+=anss[i]-bl[i]+1;
					}
				}
				if(s>=k){
					ans=md;
					R=md-1;
					for(int i=ll+1;i<rr;i++){
						ansr[i]=anss[i];
					}
				}
				else{
					L=md+1;
					for(int i=ll+1;i<rr;i++){
						ansl[i]=max(anss[i],bl[i]);
					}
				}
			}
			printf("%d\n",ans);
		}
		else{
			if(ll==rr){
				for(int i=l;i<=r;i++){
					a[i]+=k;
				}
				t1=t2=0;
				t3=br[ll];
				for(int j=bl[ll];j<=br[ll];j++){
					if(l<=b[j].p&&b[j].p<=r){
						b[j].z+=k;
						c1[++t1]=b[j];
					}
					else{
						c2[++t2]=b[j];
					}
				}
				while(t1&&t2){
					if(c1[t1].z<=c2[t2].z){
						b[t3--]=c2[t2--];
					}
					else{
						b[t3--]=c1[t1--];
					}
				}
				while(t1){
					b[t3--]=c1[t1--];
				}
				while(t2){
					b[t3--]=c2[t2--];
				}
			}
			else{
				for(int i=l;i<=br[ll];i++){
					a[i]+=k;
				}
				t1=t2=0;
				t3=br[ll];
				for(int i=bl[ll];i<=br[ll];i++){
					if(l<=b[i].p&&b[i].p<=br[ll]){
						b[i].z+=k;
						c1[++t1]=b[i];
					}
					else{
						c2[++t2]=b[i];
					} 
				}
				while(t1&&t2){
					if(c1[t1].z>c2[t2].z){
						b[t3--]=c1[t1--];
					}
					else{
						b[t3--]=c2[t2--];
					}
				}
				while(t1){
					b[t3--]=c1[t1--];
				}
				while(t2){
					b[t3--]=c2[t2--];
				}
				for(int i=bl[rr];i<=r;i++){
					a[i]+=k;
				}
				t1=t2=0;
				t3=br[rr];
				for(int i=bl[rr];i<=br[rr];i++){
					if(bl[rr]<=b[i].p&&b[i].p<=r){
						b[i].z+=k;
						c1[++t1]=b[i];
					}
					else{
						c2[++t2]=b[i];
					} 
				}
				while(t1&&t2){
					if(c1[t1].z>c2[t2].z){
						b[t3--]=c1[t1--];
					}
					else{
						b[t3--]=c2[t2--];
					}
				}
				while(t1){
					b[t3--]=c1[t1--];
				}
				while(t2){
					b[t3--]=c2[t2--];
				}
				for(int i=ll+1;i<rr;i++){
					lx[i]+=k;
				}				
			} 
		}
	}
	return 0;
}