#include <bits/stdc++.h>
using namespace std;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define min(x,y) (x<y?x:y)
#define max(x,y) (x<y?y:x)
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read(){
    int x=0;bool f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return f?x:-x;
}
int n,q,bl[100005],block=230,ad[500],l,r,mc,ld,rd,mid,c,a[100005],b[100005],opt;
inline void Add(int l,int r,int w){
    for(register int i=l;i<=r&&i<=bl[l]*block;++i)
        a[i]+=w;
    for(register int i=(bl[l]-1)*block+1;i<=n&&i<=bl[l]*block;i++)
        b[i]=a[i];
    sort(b+(bl[l]-1)*block+1,b+min(n,bl[l]*block)+1);
    if(bl[l]^bl[r]){
        for(register int i=(bl[r]-1)*block+1;i<=r;++i)
            a[i]+=w;
        for(register int i=(bl[r]-1)*block+1;i<=n&&i<=bl[r]*block;++i)
            b[i]=a[i];
        sort(b+(bl[r]-1)*block+1,b+min(n,bl[r]*block)+1);
    }
    for(register int i=bl[l]+1;i<bl[r];++i)
        ad[i]+=w;
}
inline bool check(int l,int r,int w){
    int ans=0;
    for(register int i=l;i<=r&&i<=bl[l]*block;++i)
        if(a[i]<=w-ad[bl[i]])
            ans++;
    if(bl[l]^bl[r])
        for(register int i=(bl[r]-1)*block+1;i<=r;++i)
            if(a[i]<=w-ad[bl[i]])
                ans++;
    for(register int i=bl[l]+1;i<bl[r];++i){
        ld=(i-1)*block+1,rd=i*block+1;
        if(b[ld]>w-ad[i])
            continue;
        while(ld<rd-1){
            mid=ld+rd>>1;
            if(b[mid]>w-ad[i]) rd=mid;
            else ld=mid;
        }
        ans+=ld-(i-1)*block;
        if(ans>=mc) return 1;
    }
    return ans>=mc;
}
inline int gmin(int l,int r){
    int ans=2147483647;
    for(register int i=l;i<=r&&i<=bl[l]*block;++i)
        ans=min(ans,a[i]+ad[bl[i]]);
    if(bl[l]^bl[r])
        for(register int i=(bl[r]-1)*block+1;i<=r;++i)
            ans=min(ans,a[i]+ad[bl[i]]);
    for(register int i=bl[l]+1;i<bl[r];++i)
        ans=min(ans,b[(i-1)*block+1]+ad[i]);
    return ans;
}
inline int gmax(int l,int r){
    int ans=-2147483647;
    for(register int i=l;i<=r&&i<=bl[l]*block;++i)
        ans=max(ans,a[i]+ad[bl[i]]);
    if(bl[l]^bl[r])
        for(register int i=(bl[r]-1)*block+1;i<=r;++i)
            ans=max(ans,a[i]+ad[bl[i]]);
    for(register int i=bl[l]+1;i<bl[r];++i)
        ans=max(ans,b[i*block]+ad[i]);
    return ans;
}
inline int query(int l,int r,int w){
	if(r-l+1<w||w<1) return -1;
    int lv=gmin(l,r),rv=gmax(l,r),ans=-1;
    if(r-l+1==w) return rv;
    if(w==1) return lv;
    while(lv<=rv){
        int mid=1ll*(lv+rv)>>1;
        if(check(l,r,mid)) rv=(ans=mid)-1;
        else lv=mid+1;
    }
    return ans;
}
int main(){
// 	freopen("a.in","r",stdin);
// 	freopen("a.out","w",stdout);
    n=read(),q=read();
    for(register int i=1;i<=n;++i)
        a[i]=read(),bl[i]=(i-1)/block+1,b[i]=a[i];
    for(register int i=1;i<=bl[n];++i)
        sort(b+(i-1)*block+1,b+min(n,i*block)+1);
    while(q--){
        opt=read(),l=read(),r=read(),mc=read();
        if(opt&1) printf("%d\n",query(l,r,mc));
        else Add(l,r,mc);
    }
    return 0;
}