rt.

#include<bits/stdc++.h>
//#include<windows.h>
using namespace std;
#define int long long
const int maxn=1e5+10;
int n,m,len,siz,a[maxn],num[maxn];
struct node{int id,cnt;}v[maxn];
int l[maxn],r[maxn],tag[maxn];
inline int read(){
   int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
inline void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x % 10+'0');
}
inline void get_sort(int l,int r,int k){
	for(int i=(num[l]-1)*len+1;i<=min(num[r]*len,n);++i){
//		cout << len << " " << l << " " << r << " " << v[i].id << " " << v[i].cnt << " " << v[i+1].id << " check" << endl;
		if(l<=v[i].id && v[i].id<=r){/*cout << "now " << v[i].id << " " << v[i].cnt << " " << l << " " << r << "  "<< k << endl;*/v[i].cnt+=k,a[v[i].id]+=k;}
	}
	sort(v+(num[l]-1)*len+1,v+min(num[l]*len,n)+1,[](node x,node y){return x.cnt<y.cnt;});
}
inline void add(int l,int r,int kk){
	if(num[l]==num[r]){/*puts("hihihihhihihihihihih");*/get_sort(l,r,kk);return ;}
	for(int k=num[l]+1;k<num[r];++k)tag[k]+=kk;
	get_sort(l,num[l]*len,kk);get_sort((num[r]-1)*len+1,r,kk);
}
inline int find(int l,int r,int kk){
	if(r-l+1<kk)return -1;
	if(num[l]==num[r]){
		vector<int>e;for(int i=0;i<=r-l;++i)e.push_back(a[i+l]);
		sort(e.begin(),e.end());return e[kk-1]+tag[num[l]];
	}
	int L=2e9,R=-2e9;
	L=min({L,v[l].cnt+tag[num[l]],v[(num[r]-1)*len+1].cnt+tag[num[r]]});
	R=max({R,v[num[l]*len].cnt+tag[num[l]],v[min(num[r]*len,r)].cnt+tag[num[r]]});
	for(int i=num[l]+1;i<num[r];++i){L=min(l,v[(i-1)*len+1].cnt+tag[i]);R=max(R,v[i*len+1].cnt+tag[i]);}
	while(L<R){
		int mid=((L+R)>>1);int cnt=0;
//		cout << mid << " put" << endl;
		if(num[l]!=num[r]){
			for(int k=num[l]+1;k<num[r];++k){
				if(v[k*len].cnt+tag[k]<=mid)cnt+=len;
				else if(v[(k-1)*len+1].cnt+tag[k]<=mid){
					int l1=(k-1)*len+1,r1=k*len;
					while(l1<r1){
						int mid=(l1+r1)>>1;
	//					cout << l1 << " " << r1 << " " << mid << " put1" << endl;Sleep(500);
						if(v[mid].cnt+tag[k]>=mid)r1=mid;
						else l1=mid+1;
					}
					cnt+=l1-(k-1)*len;
				}
			}
//			cout << "hi" << l << " " << r << " " << num[l] << " " << num[r] << endl;
			for(int k=(num[l]-1)*len+1;k<=num[l]*len;++k)if(l<=v[k].id && v[k].cnt+tag[num[k]]<=mid)++cnt;
			for(int k=((num[r]-1)*len+1);k<=min(n,num[r]*len);++k)if(v[k].id<r && v[k].cnt+tag[num[r]]<=mid)++cnt;
		}else for(int i=(num[l]-1)*len+1;i<=min(n,num[r]*n);++i)if(l<=v[i].id && v[i].id<=r && v[i].cnt+tag[num[i]]<=mid)++cnt;

//		cout << "wcnm " << L << " " << R << " " << cnt << endl;
		if(cnt>=kk)R=mid;
		else L=mid+1;
	}
	return L;
}
inline void out_put(){for(int i=1;i<=n;++i)cout << "fuck " << v[i].cnt << " " << v[i].id << endl;}
signed main(){
//	freopen("4.in","r",stdin);
	n=read(),m=read();len=sqrt(n);for(int i=1;i<=n;++i){a[i]=read();v[i].id=i,v[i].cnt=a[i];num[i]=(i-1)/len+1;}
	siz=n/len;if(n%len!=0)siz++;for(int i=1;i<siz;++i){sort(v+((i-1)*len+1),v+(i*len)+1,[](node x,node y){return x.cnt<y.cnt;});}
//	puts("now");
	sort(v+(num[n]-1)*len+2,v+n+1,[](node x,node y){return x.cnt<y.cnt;});
//	puts("hi");
	for(int i=1;i<=m;++i){/*out_put();*/int op,l,r,k;op=read(),l=read(),r=read(),k=read();if(op==1){printf("%lld\n",find(l,r,k));/*write(find(l,r,k));putchar('\n');*/}else add(l,r,k);}	
	return 0;
}