#include<bits/stdc++.h>
#define reg register int
#define INF (1<<30)
#define int long long 

//#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[200005]; 
int n,cnt,m,a[200005],ans,tmp,l,r,k,z,x[200005],y[200005],id[200005],v[1010];
int ks[1005][1005];
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[1005];
    for(int i=x[ll];i<=y[ll];i++) t[i-x[ll]+1]=a[i]+lazy[ll];
    sort(t+1,t+y[ll]-x[ll]+1+1);
    for(int i=x[ll];i<=t[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]+lazy[rr];
    sort(t+1,t+y[rr]-x[rr]+1+1);
    for(int i=x[rr];i<=t[rr];i++) ks[rr][i-x[rr]+1]=t[i-x[rr]+1];
//	memset()
}
inline int cx(int l,int r,int k){
	if(r-l+1<k) return -1;
	int kl=id[l]+1,kr=id[r]-1;
	int xx=l,yy=x[kr]+1;
	int tmp1[1010],tmp2[1010];
	for(int i=y[kr]+1;i<=r;i++) tmp2[i]=a[i];
	for(int i=xx;i<=x[kl]-1;i++) tmp1[i]=a[i];
	int len=r-(y[kr]+1)+1;
	sort(tmp1+1,tmp1+len+1);
	len=x[kl]-1-xx+1;
	sort(tmp2+1,tmp2+len+1);
	/*
	查询时加lazy！！！！！！！114514 
	*/
	xx=1,yy=1;
	int d[1005];
	memset(d,0,sizeof(d));
	int xuan=INF,xid=0;
    for(int aaa=1;aaa<=k;aaa++){
    	xuan=INF;
    	for(int i=kl;i<=kr;i++){
//    		xuan=min(xuan,a[d[i]+1]+lazy[i])
			if(xuan>ks[i][d[i]+1]+lazy[i]&&d[i]+1<=y[i]-x[i]+1){
				xuan=ks[i][d[i]+1]+lazy[i];
				xid=i;
			}
		}//整块 
//			cout<<a[xx]<<' '<<a[yy]<<endl;
			if(xuan>tmp1[xx]+lazy[id[xx]]){
				xuan=tmp1[xx]+lazy[id[xx]];
				if(!(xuan>tmp2[yy]+lazy[id[yy]])) {
					xx++;
					continue;
				}else{
					yy++;
					continue;
				}
//				xid=i;
			}
			if(xuan>tmp2[yy]+lazy[id[yy]]){
				yy++;
				continue;
			}//散块
			 
		d[xid]++;
	}
	return xuan;
}

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[1005];
        for(int j=x[i];j<=y[i];j++) {
        	id[j]=i,v[i]+=a[j];
//        	ks[i][j-x[i]+1]=a[j];
			t[j-x[i]+1]=a[j];
		}
//		sort(ks+x[i],ks+y[i]-x[i]+1+1);
		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
    */
//    for(int i=1;i<=S;i++){
//    	
//    	for(int j=1;j<=y[i]-x[i]+1;j++) cout<<ks[i][j]<<' ';
//    	cout<<endl;
//    	
//	}

    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;
}

目前注释里的样例过不去，提交全RE/dk/dk/dk