rt，应该只有一个小细节挂了。实在调不来了，一些优化还没加，卡常自己卡，主要是代码能找个错嘛/kel

#include<bits/stdc++.h>
#define reg register int
#define INF (1<<30)
//#define int long long 
#pragma GCC target("avx,avx2")
#define ts cout<<"qyhakioi\n";
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 
using namespace std;

const int inf=1e9;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
int read(){
    int res=0,fs=1; char c=getchar();
    while(!(c>='0' && c<='9')){ if(c=='-')fs=-1; c=getchar(); }
    while(c>='0' && c<='9')res=res*10+(c^48),c=getchar();
    return res*fs;
}
void print(int x){
    if(x<0) { putchar('-'); x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int S;
int lazy[100005]; 
int n,cnt,m,a[100005],ans,tmp,l,r,k,z,x[100005],y[100005],id[100005],v[1010];
int ks[320][320];
inline void sh(int l,int r,int k){ 

    int ll=id[l],rr=id[r]; 
    for(int i=ll+1;i<=rr-1;i++) lazy[i]+=k;
    for(int i=l;i<=y[ll];i++) {
    	a[i]+=k;
	}
	for(int i=x[rr];i<=r;i++) {
    	a[i]+=k;
	}
	
    int t[320];
    for(int i=x[ll];i<=y[ll];i++) t[i-x[ll]+1]=a[i];

    sort(t+1,t+y[ll]-x[ll]+1+1);
    for(int i=x[ll];i<=y[ll];i++) ks[ll][i-x[ll]+1]=t[i-x[ll]+1];
    
//    memset(t,0,sizeof(t));
    for(int i=x[rr];i<=y[rr];i++) t[i-x[rr]+1]=a[i];
    sort(t+1,t+y[rr]-x[rr]+1+1); 
    for(int i=x[rr];i<=y[rr];i++) ks[rr][i-x[rr]+1]=t[i-x[rr]+1];
//	memset()
}
int qaq(int i,int v){
	
	int l=1,r=y[i]-x[i]+1;
	while(l<r){
		int mid=(l+r+1)/2;
		if(ks[i][mid]+lazy[i]>v) r=mid-1;
		else l=mid;
		//                cout<<"1111";
	}
	return l;
			
} 
inline int cx(int ll,int rr,int k){
	
	if(ll==rr){
//		return
		if(k>=2) return -1;
		return a[ll]+lazy[id[ll]]; 
	}
	int kx=id[ll],ky=id[rr];
	int l=-3e4,r=3e4;
	int ret=-1;
//	cout<<kx
	while(l<=r){
		int mid=(l+r)/2;
//		ts
		int cnt=0;
		
		for(int i=ll;i<=y[kx];i++) if(a[i]+lazy[kx]<=mid) cnt++;
		if(kx!=ky)
		for(int i=x[ky];i<=rr;i++) if(a[i]+lazy[ky]<=mid) cnt++;
		
//		cout<<l<<' '<<r<<' '<<cnt<<' ';
		for(int i=kx+1;i<=ky-1;i++){
			cnt+=qaq(i,mid);
//			ts
		}	
//		cout<<cnt<<'\n';
		if(cnt>=k) r=mid-1,ret=mid;
		else l=mid+1;
	}
	return ret;
}

signed main() { 
    cin>>n>>m;  
    for(int i=1;i<=n;i++) a[i]=read();
    S=sqrt(n); 
    for(int i=1;i<=S;i++){
        x[i]=(i-1)*S+1,y[i]=min(i*S,n);
    } 
    if(x[S]<n) S++,x[S]=y[S-1]+1,y[S]=n; 
    for(int i=1;i<=S;i++){ 
    	int t[320];
        for(int j=x[i];j<=y[i];j++) {
        	id[j]=i,v[i]+=a[j]; 
			t[j-x[i]+1]=a[j];
		} 
		sort(t+1,t+y[i]-x[i]+1+1);
		for(int j=1;j<=y[i]-x[i]+1;j++) ks[i][j]=t[j]; 
    } 
    /*
    10 10
	15 11 -18 12 6 9 14 -2 -10 6
	1 2 3 1
	2 2 4 -3
	1 4 10 7
	1 2 2 1
	1 8 8 1
	2 4 10 4
	1 4 10 1
	1 7 10 4
	2 1 4 -5
	1 1 8 4
    */ 
    while(m--){
        int op;
        cin>>op;
        if(op==2){
        	l=read(),r=read(),k=read();
            sh(l,r,k); 
        }else if(op==1){
        	l=read(),r=read(),k=read();
            cout<<cx(l,r,k)<<'\n';
        } 
    }
    return 0;
}