#include<stdio.h>
#include<algorithm>
#include<queue>
#include<ctype.h>
namespace fasti{
	char buf[1<<21],*p1=buf,*p2=buf;
	inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*(p1++);}
	inline void read(int&x){
        char c=getc(),f=0;
        for(;!isdigit(c);c=getc())f^=!(c^'-');
        for(x=0;isdigit(c);c=getc())x=x*10+(c^48);
        if(f)x=-x;--p1;
	}
	template<typename... Args>
	inline void read(int&x,Args&...args){read(x),read(args...);}
}
using fasti::getc;
using fasti::read;
const int bl=200;
int a[100001],b[100001],tag[100001],n;
bool cmp(const int&x,const int&y){return a[x]<a[y];}
void add(int t,int l,int r,int k){
    static std::queue<int>p,q;
    for(int i=(t-1)*bl+1;i<=t*bl&&t<=n;++i)
        if(l<=b[i]&&b[i]<=r)
            a[b[i]]+=k,p.push(b[i]);
        else
            q.push(b[i]);
    int s=(t-1)*bl+1;
    for(;p.size()&&q.size();)
        if(cmp(p.front(),q.front()))
            b[s++]=p.front(),p.pop();
        else
            b[s++]=q.front(),q.pop();
    for(;p.size();p.pop())b[s++]=p.front();
    for(;q.size();q.pop())b[s++]=q.front();
}
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}
int getmin(int l,int r){
    if((l-1)/bl!=(r-1)/bl){
        int res=2147483647,L=((l+bl-2)/bl)*bl+1,R=(r/bl)*bl;
        for(int i=l;i<L;++i)res=min(res,a[i]+tag[(i+bl-1)/bl]);
        for(int i=R+1;i<=r;++i)res=min(res,a[i]+tag[(i+bl-1)/bl]);
        for(int i=L;i<=R;i+=bl)res=min(res,a[b[i]]+tag[i/bl+1]);
        return res;
    }else{
        int res=2147483647;
        for(int i=l;i<=r;++i)res=min(res,a[i]+tag[(i+bl-1)/bl]);
        return res;
    }
}
int getmax(int l,int r){
    if((l-1)/bl!=(r-1)/bl){
        int res=-2147483648,L=((l+bl-2)/bl)*bl+1,R=(r/bl)*bl;
        for(int i=l;i<L;++i)res=max(res,a[i]+tag[(i+bl-1)/bl]);
        for(int i=R+1;i<=r;++i)res=max(res,a[i]+tag[(i+bl-1)/bl]);
        for(int i=L;i<=R;i+=bl)res=max(res,a[b[min(i+bl-1,n)]]+tag[i/bl+1]);
        return res;
    }else{
        int res=-2147483648;
        for(int i=l;i<=r;++i)res=max(res,a[i]+tag[(i+bl-1)/bl]);
        return res;
    }
}
int rnk(int l,int r,int k){
    if((l-1)/bl!=(r-1)/bl){
        int res=0,L=((l+bl-2)/bl)*bl+1,R=(r/bl)*bl;
        for(int i=l;i<L;++i)if(a[i]+tag[(i+bl-1)/bl]<k)++res;
        for(int i=R+1;i<=r;++i)if(a[i]+tag[(i+bl-1)/bl]<k)++res;
        for(int i=L;i<=R;i+=bl)
            a[0]=k-tag[i/bl+1],res+=std::lower_bound(b+i,b+(i+bl-1>n?n:i+bl-1)+1,0,cmp)-b-i;
        return res;
    }else{
        int res=0;
        for(int i=l;i<=r;++i)if(a[i]+tag[(i+bl-1)/bl]<k)++res;
        return res;
    }
}
int main(){
    int m;
    read(n,m);
    for(int i=1;i<=n;++i)read(a[i]),b[i]=i;
    for(int i=1;(i-1)*bl<n;++i)std::sort(b+(i-1)*bl+1,b+(i*bl>n?n:i*bl)+1,cmp);
    for(int op,l,r,k;m--;){
        read(op,l,r,k);
        if(op==1){
            if(k<1||k>(r-l+1))puts("-1");
            else{
                --k;
                int L=getmin(l,r),R=getmax(l,r);
                for(;L<R;){
                    int mid=(1ll+L+R)>>1,t=rnk(l,r,mid);
                    if(t<=k)L=mid;
                    else R=mid-1;
                }
                printf("%d\n",L);
            }
        }else{
            if((l-1)/bl!=(r-1)/bl){
                int L=((l+bl-2)/bl)*bl+1,R=(r/bl)*bl;
                if(l<L)add(L/bl,l,L-1,k);
                if(R<r)add(R/bl+1,R+1,r,k);
                for(int i=L;i<=R;i+=bl)tag[i/bl+1]+=k;
            }else add((l-1)/bl+1,l,r,k);
        }
    }
    return 0;
}

目前测试发现当块长取 $200$ 时最优，而当块长取 $300$ 时会出现玄学 WA 和 RE

区间加和查询排名的代码通过了教主的魔法那题，所以应该是没问题的，但是看起来我的二分也没挂啊……