UPD2: 实际上，只要把 $\frac 13$ 换成更小的数平衡常数就能通过此题，现在的代码已更换可以通过的选择的数为 $\frac 1{10}$。

UPD: 在大佬 @DPair 的卡常帮助下，这个算法可以通过本题，提交记录。

本篇题解将会给出 $\mathrm O(n\sqrt{n\log n})$ 的做法和参考实现，不过我的实现不够精细，被卡常了。

我们发现原做法的复杂度瓶颈在查询时的多序列二分，考虑用分散层叠优化，不会分散层叠的可以先看这题。

因为带修，所以我们要换一种合并方式，考虑线段树，每个叶子节点存放一块序列，非叶节点合并子节点序列各 $\frac{1}{3}$，这样修改时重构的复杂度为 $\mathrm O(B+\frac{2}{3}B+\frac{4}{9}B+…)=O(B)$。

查询时遍历整颗线段树就行。$B$ 取 $O(\sqrt{n\log n})$ 最优。

具体的看代码就行了：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
namespace IO{
	#define BUFSIZE 10000000
	struct read{
		char buf[BUFSIZE],*p1,*p2,c,f;
		read():p1(buf),p2(buf){}
		inline char gc(void){
			return p1==p2&&(p2=buf+fread(p1=buf,1,BUFSIZE,stdin),p1==p2)?EOF:*p1++;
		}
		inline read& operator >>(int& x){
			for(c=gc(),f=0,x=0;c!=EOF&&(c<'0'||c>'9');c=gc())if(c=='-')f=1;
			if(f)for(;c>='0'&&c<='9';c=gc())x=x*10-(c-'0');
			else for(;c>='0'&&c<='9';c=gc())x=x*10+(c-'0');
			return *this;
		}
	}in;
	struct write{
		char buf[BUFSIZE],*p1,*p2,s[50],f;
		int tp;
		write():p1(buf){}
		~write(){fwrite(buf,1,p1-buf,stdout);}
		inline write& operator <<(int x){
			if(x<0)f=1,*p1++='-';else f=0;
			if(f)do{s[tp++]=-x%10+'0',x/=10;}while(x);
			else do{s[tp++]=x%10+'0',x/=10;}while(x);
			while(tp)*p1++=s[--tp];
			return *this;
		}
		inline write& operator <<(char const &x){
			*p1++=x;
			return *this;
		}
	}out;
}
using IO::in;
using IO::out;
int n,m,a[100010],B,bel[100010],bcnt,L[510],R[510];
struct node{
	int v,nxt1,nxt2;
	node():v(),nxt1(),nxt2(){}
	node(int const &x):v(x),nxt1(),nxt2(){}
	node(int const &x,int const &i):v(x),nxt1(i),nxt2(){}
	bool operator <(node const &x)const{return v<x.v;} 
}pool[300010],*it=pool,*tr[2010];
int tag[2010],sz[2010];
inline void build(int x=1,int l=1,int r=bcnt){
	if(l==r){
		tr[x]=it;
		for(int i=L[l];i<=R[l];i++)it[i-L[l]]=node(a[i],i);
		sz[x]=R[l]-L[l]+2;
		it+=sz[x]-1;
		*it++=node(0x7fffffff);
		std::sort(tr[x],it);
		return;
	}
	int ls=x<<1,rs=x<<1|1,mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	static node tmp1[10010],tmp2[10010];
	node *it1=tmp1,*it2=tmp2;
	for(int i=0;i<sz[ls]-1;i+=10)*it1++=tr[ls][i].v;
	for(int i=0;i<sz[rs]-1;i+=10)*it2++=tr[rs][i].v;
	std::merge(tmp1,it1,tmp2,it2,tr[x]=it);
	int &len=sz[x]=it1-tmp1+it2-tmp2+1;
	it+=len-1;
	*it++=node(0x7fffffff);
	int i=0,j=0;
	while(i<len&&j<sz[ls])if(tr[x][i].v<=tr[ls][j].v) tr[x][i++].nxt1=j;else j++;
	i=0,j=0;
	while(i<len&&j<sz[rs])if(tr[x][i].v<=tr[rs][j].v) tr[x][i++].nxt2=j;else j++;
}
inline void update(int pl,int pr,int k,int x=1,int l=1,int r=bcnt){
	if(pl==L[l]&&pr==R[r]) return tag[x]+=k,void();
	static node tmp1[10010],tmp2[10010];
	node *it1=tmp1,*it2=tmp2;
	if(l==r){
		for(int i=0;i<sz[x]-1;i++)
			if(tr[x][i].nxt1<=pr&&tr[x][i].nxt1>=pl)*it1++=node(tr[x][i].v+k,tr[x][i].nxt1);
			else *it2++=node(tr[x][i].v,tr[x][i].nxt1);
		*it2++=node(0x7fffffff);
		std::merge(tmp1,it1,tmp2,it2,tr[x]);
		return;
	}
	int ls=x<<1,rs=x<<1|1,mid=(l+r)>>1;
	if(pr<=R[mid]) update(pl,pr,k,ls,l,mid);
	else if(pl>R[mid]) update(pl,pr,k,rs,mid+1,r);
	else update(pl,R[mid],k,ls,l,mid),update(R[mid]+1,pr,k,rs,mid+1,r);
	for(int i=0;i<sz[ls]-1;i+=10)*it1++=tr[ls][i].v+tag[ls];
	for(int i=0;i<sz[rs]-1;i+=10)*it2++=tr[rs][i].v+tag[rs];
	*it2++=node(0x7fffffff);
	std::merge(tmp1,it1,tmp2,it2,tr[x]);
	int &len=sz[x];
	int i=0,j=0;
	while(i<len&&j<sz[ls]-1)if(tr[x][i].v<=tr[ls][j].v+tag[ls]) tr[x][i++].nxt1=j;else j++;
	while(i<len)tr[x][i++].nxt1=sz[ls]-1;
	i=0,j=0;
	while(i<len&&j<sz[rs]-1)if(tr[x][i].v<=tr[rs][j].v+tag[rs]) tr[x][i++].nxt2=j;else j++;
	while(i<len)tr[x][i++].nxt2=sz[rs]-1;
}
int d1[10010],d2[10010],d[20010];
int *c1;
inline void collect(int pl,int pr,int v=0,int x=1,int l=1,int r=bcnt){
	if(l==r){
		for(int i=0;i<sz[x];i++)
			if(tr[x][i].nxt1<=pr&&tr[x][i].nxt1>=pl) *c1++=tr[x][i].v+v+tag[x];
		return;
	}
	int ls=x<<1,rs=x<<1|1,mid=(l+r)>>1;
	if(pr<=R[mid]) collect(pl,pr,v+tag[x],ls,l,mid);
	else collect(pl,pr,v+tag[x],rs,mid+1,r);
}
inline int query(int pl,int pr,int v,int k,int x=1,int l=1,int r=bcnt){
	while(k&&tr[x][k-1].v>v-tag[x])--k;
	if(l==r) return k;
	int ls=x<<1,rs=x<<1|1,mid=(l+r)>>1;
	if(pr<=mid) return query(pl,pr,v-tag[x],tr[x][k].nxt1,ls,l,mid);
	if(pl>mid) return query(pl,pr,v-tag[x],tr[x][k].nxt2,rs,mid+1,r);
	return query(pl,mid,v-tag[x],tr[x][k].nxt1,ls,l,mid)+query(mid+1,pr,v-tag[x],tr[x][k].nxt2,rs,mid+1,r); 
}
inline int getans(int pl,int pr,int k){
	if(pl>pr) return 0;
	return query(pl,pr,k,std::upper_bound(tr[1],tr[1]+sz[1],node(k))-tr[1]);
}
int main(){
	in>>n>>m;
	B=sqrt(n*log2(n));if(!B)B=1;
	for(int i=1;i<=n;i++)in>>a[i],bel[i]=(i-1)/B+1;
	for(int i=1;i<=n;i++)R[bel[i]]=i;
	for(int i=n;i;i--)L[bel[i]]=i;
	bcnt=bel[n];
	build();
	while(m--){
		int op,l,r,k;
		in>>op>>l>>r>>k;
		if(op==1){
			if(r-l+1<k)out<<-1;
			else{
				int x=0x8000000f,y=-x,ans=0,mid;
				if(bel[l]==bel[r]){
					c1=d,collect(l,r);
					while(x<=y){ 
						mid=(1ll*x+y)>>1;
						if(std::upper_bound(d,c1,mid)-d>=k)ans=mid,y=mid-1;
						else x=mid+1;
					}
				}else{
					c1=d1,collect(l,R[bel[l]]);
					c1=d2,collect(L[bel[r]],r);
					std::merge(d1,d1+R[bel[l]]-l+1,d2,d2+r-L[bel[r]]+1,d);
					c1=d+R[bel[l]]-l+1+r-L[bel[r]]+1;
					while(x<=y){
						mid=(1ll*x+y)>>1;
						if(std::upper_bound(d,c1,mid)-d+getans(bel[l]+1,bel[r]-1,mid)>=k)ans=mid,y=mid-1;
						else x=mid+1;
					}
				}
				out<<ans<<'\n';
			}
		}else update(l,r,k);
	}
	return 0;
}