RT

#include <bits/stdc++.h>
using namespace std;
const int maxn=110005;
const int maxm=405;
int n,m,block;
int a[maxn],p[maxm][maxm],tag[maxn],pos[maxn],L[maxm],R[maxm];
struct nod{
	int pos,val;
}sav[maxn];
inline bool cmp(nod x,nod y){return x.val<y.val;}
inline int read(){
	int ret=0,f=1;	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
int check(int val,int l,int r){
	int sum=0;
	if(pos[l]==pos[r]){
		for(int k=l;k<=r;k++)	sum+=(a[k]<=val);
		return sum;
	}
	int rr=R[pos[l]],ll=L[pos[r]],tl=tag[pos[l]],tr=tag[pos[r]];
	for(int k=l;k<=rr;k++)  sum+=(a[k]<=val-tl);
	for(int k=ll;k<=r;k++)  sum+=(a[k]<=val-tr);
//	if(val<=10)	cout<<"val= "<<val<<" "<<sum<<endl;
	for(int k=pos[l]+1;k<=pos[r]-1;k++){
		int l=0,r=block,ans=0,w=val-tag[k];
		while(l<r){
			int mid=l+r+1>>1;
			if(a[p[k][mid]]<=w)  l=mid;
			else    r=mid-1;
		}
		sum+=l;
//		if(val<=10) cout<<l<<" "<<k<<endl;
	}
//	if(val<=10)	cout<<"sum= "<<sum<<endl;
	return sum;
}
void merge(int l,int r){
	int q=pos[l];   int x,y,now;
	for(x=1,y=1,now=0;x<=block&&y<=block;){
		while(p[q][x]< l||p[q][x]> r&&x<=block) ++x;
		while(p[q][y]>=l&&p[q][y]<=r&&y<=block) ++y;
		if(x>block||y>block)    break;
		if(a[p[q][x]]<a[p[q][y]])
		sav[++now].val=p[q][x++];
		else
		sav[++now].val=p[q][y++];
	}
	while(x<=block){
		while(p[q][x]<l||p[q][x]>r) 	++x;
		sav[++now].val=p[q][x++];
	}
	while(y<=block){
		while(p[q][y]>=l&&p[q][y]<=r)   ++y;
		sav[++now].val=p[q][y++];
	}
	for(int k=1;k<=block;k++) p[q][k]=sav[k].val;
}
void prework(){
	for(int k=1;k<=n;k++)	pos[k]=(k-1)/block+1;
	for(int k=1;k<=pos[n];k++){
		int r=k*block,l=r-block+1;
		L[k]=l;	R[k]=r;
		for(int j=l;j<=r;j++)
		sav[j].val=a[j],
		sav[j].pos=j;
		sort(sav+l,sav+r+1,cmp);
		for(int j=l;j<=r;j++)
		p[k][j-l+1]=sav[j].pos;
	}
}
void solve(){
	for(int k=1;k<=m;k++){
		int opt,l,r,val;
		opt=read(); l=read();   r=read();   val=read();
		if(opt==1){
			int ll=-(int)(2e9),rr=(int)(2e9);
			while(ll<rr){
				int mid=ll+rr>>1;
//				cout<<l<<" "<<r<<" "<<mid<<" "<<ll<<" "<<rr<<endl;
				if(check(mid,l,r)<val)  ll=mid+1;
				else    rr=mid;
				
			}
			if(k%10000==0)
			if(abs(ll)==(int)(2e9))    puts("-1");
			else	printf("%d\n",ll);
		}
		else{
			if(pos[l]==pos[r]){
				for(int k=l;k<=r;k++)   a[k]+=val;
				merge(l,r);
			}
			else{
				int ll=L[pos[r]],rr=R[pos[l]];
				for(int k=l;k<=rr;k++)  a[k]+=val;
				for(int k=ll;k<=r;k++)  a[k]+=val;
				merge(l,rr);    merge(ll,r);
				for(int k=pos[l]+1;k<=pos[r]-1;k++) tag[k]+=val;
			}
		}
//		for(int j=1;j<=pos[n];j++)  cout<<p[j][1]<<" "<<p[j][2]<<" ";
//		cout<<endl;
//		for(int j=1;j<=n;j++)   cout<<a[j]+tag[pos[j]]<<" ";
//		cout<<endl;
	}
}
signed main(){
	freopen("1.in","r",stdin);
	n=read();   m=read();   block=sqrt(n);
	for(int k=1;k<=n;k++)	a[k]=read();
	prework();  solve();
	return 0;
}