RT，不知道为啥小数据WA掉了

#pragma GCC optimize("Ofast",2,3)
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],s[100005],lazy[100005];
int begin[100005],end[100005],block;
inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0') {
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0') {
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*f;
}
void build() {
	block=sqrt(n);
	int num=1;
	for(int i=1; i<=n; i+=block) {
		begin[num]=i;
		end[num]=min(n,i+block-1);
		sort(s+i,s+end[num]+1);
		num++;
	}
	return;
}
inline void msort(int l1,int r1,int l2,int r2) {
	int i=l1,j=l2,k=l1;
	while(i<=r1&&j<=r2) {
		if(a[i]<a[j])s[k++]=a[i++];
		else s[k++]=a[j++];
	}
	while(i<=r1)s[k++]=a[i++];
	while(j<=r2)s[k++]=a[j++];
	return;
}
inline void update(int l,int r,int k) {
	int numl=(l/block)+(l%block!=0);
	int numr=(r/block)+(r%block!=0);
	if(numl==numr) {
		for(int i=l; i<=r; i++)a[i]+=k;
		if(lazy[numl])
			for(int i=begin[numl]; i<=end[numl]; i++)
				a[i]+=lazy[numl];
		if(l!=begin[numl])msort(begin[numl],l-1,l,r);
		if(r!=end[numl])msort(begin[numl],r,r+1,end[numl]);
		lazy[numl]=0;
		return;
	}
	for(int i=l; i<=end[numl]; i++)a[i]+=k;
	if(lazy[numl])
		for(int i=begin[numl]; i<=end[numl]; i++)
			a[i]+=lazy[numl];
	if(l!=begin[numl])msort(begin[numl],l-1,l,end[numl]);
	for(int i=begin[numr]; i<=r; i++)a[i]+=k;
	if(lazy[numr])
		for(int i=begin[numr]; i<=end[numr]; i++)
			a[i]+=lazy[numr];
	if(r!=end[numr])msort(begin[numl],r,r+1,end[numl]);
	lazy[numl]=lazy[numr]=0;
	for(int i=numl+1; i<numr; i++)lazy[i]+=k;
}
inline int rank(int l,int r,int k) {
	int numl=(l/block)+(l%block!=0);
	int numr=(r/block)+(r%block!=0);
	int ans=1,p;
	if(numl==numr) {
		for(int i=l; i<=r; i++)if(a[i]+lazy[numl]<k)ans++;
		return ans;
	}
	for(int i=l; i<=end[numl]; i++)if(a[i]+lazy[numl]<k)ans++;
	for(int i=begin[numr]; i<=r; i++)if(a[i]+lazy[numr]<k)ans++;
	for(int i=numl+1; i<numr; i++) {
		p=lower_bound(s+begin[i],s+end[i]+1,k-lazy[i])-s;
		if(p>=begin[i])ans+=p-begin[i];
	}
	return ans;
}
int nxt(int l,int r,int k) {
	int numl=l/block+(l%block!=0);
	int numr=r/block+(r%block!=0);
	int ans=2147483647;
	if(numl==numr) {
		for(int i=l; i<=r; i++)if(a[i]+lazy[numl]>=k)ans=min(ans,a[i]+lazy[numl]);
		return ans;
	}
	for(int i=l; i<=end[numl]; i++)if(a[i]+lazy[numl]>=k)ans=min(ans,a[i]+lazy[numl]);
	for(int i=begin[numr]; i<=r; i++)if(a[i]+lazy[numr]>=k)ans=min(ans,a[i]+lazy[numr]);
	for(int i=numl+1; i<numr; i++) {
		int p=lower_bound(s+begin[i],s+end[i]+1,k-lazy[i])-s;
		if(p>=begin[i]&&p<=end[i]&&s[p]+lazy[i]>=k)ans=min(ans,s[p]+lazy[i]);
	}
	return ans;
}
inline int val(int l,int r,int k) {
	if(k>r-l+1)return -1;
	int L=-2147483647,R=2147483647,ans;
	while(L<=R) {
		int mid=(L+R)>>1;
		if(rank(l,r,mid)<=k)ans=mid,L=mid+1;
		else R=mid-1;
	}
	ans=nxt(l,r,ans);
	return ans;
}
int main() {
	n=read(),m=read();
	for(int i=1; i<=n; i++)s[i]=a[i]=read();
	build();
	int opt,l,r,k;
	while(m--) {
		opt=read(),l=read(),r=read(),k=read();
		if(opt==1)printf("%d\n",val(l,r,k));
		if(opt==2)update(l,r,k);
	}
}