已经重构2遍，前前后后提交快40遍了，全WA/dk

#include <bits/stdc++.h>
using namespace std;
const int inf=2147483647;

int n,m;

int a[100005];

int block,bcnt;
int b[100005];
int bl[100005],br[100005];
int bid[100005];
int lazy[100005];

void modify(int l,int r,int d) {
	if(bid[r]-bid[l]<=2) {
		for(int i=l;i<=r;i++) {
			a[i]+=d;
		}
		for(int i=bid[l];i<=bid[r];i++) {
			for(int j=bl[i];j<=br[i];j++) {
				b[j]=a[j];
			}
			sort(b+bl[i],b+br[i]+1);
		}
		return;
	}
	for(int i=l;i<=br[bid[l]];i++) {
		a[i]+=d;
	}
	for(int i=bl[bid[l]];i<=br[bid[l]];i++) {
		b[i]=a[i];
	}
	sort(b+bl[bid[l]],b+br[bid[l]]+1);
	for(int i=bl[bid[r]];i<=r;i++) {
		a[i]+=d;
	}
	for(int i=bl[bid[r]];i<=br[bid[r]];i++) {
		b[i]=a[i];
	}
	sort(b+bl[bid[r]],b+br[bid[r]]+1);
	for(int i=bid[l]+1;i<=bid[r]-1;i++) {
		lazy[i]+=d;
	}
}

int minq(int l,int r) {
	if(bid[r]-bid[l]<=2) {
		int res=inf;
		for(int i=l;i<=r;i++) {
			res=min(res,a[i]+lazy[bid[i]]);
		}
		return res;
	}
	int res=inf;
	for(int i=l;i<=br[bid[l]];i++) {
		res=min(res,a[i]+lazy[bid[i]]);
	}
	for(int i=bl[bid[r]];i<=r;i++) {
		res=min(res,a[i]+lazy[bid[i]]);
	}
	for(int i=bid[l]+1;i<=bid[r]-1;i++) {
		res=min(res,b[bl[i]]+lazy[i]);
	}
	return res;
}

int maxq(int l,int r) {
	if(bid[r]-bid[l]<=2) {
		int res=-inf;
		for(int i=l;i<=r;i++) {
			res=max(res,a[i]+lazy[bid[i]]);
		}
		return res;
	}
	int res=-inf;
	for(int i=l;i<=br[bid[l]];i++) {
		res=max(res,a[i]+lazy[bid[i]]);
	}
	for(int i=bl[bid[r]];i<=r;i++) {
		res=max(res,a[i]+lazy[bid[i]]);
	}
	for(int i=bid[l]+1;i<=bid[r]-1;i++) {
		res=max(res,b[br[i]]+lazy[i]);
	}
	return res;
}

int rankq(int l,int r,int d) {
	if(bid[r]-bid[l]<=2) {
		int res=0;
		for(int i=l;i<=r;i++) {
			res+=(a[i]+lazy[bid[i]]<d);
		}
		return res;
	}
	int res=0;
	for(int i=l;i<=br[bid[l]];i++) {
		res+=(a[i]+lazy[bid[i]]<d);
	}
	for(int i=bl[bid[r]];i<=r;i++) {
		res+=(a[i]+lazy[bid[i]]<d);
	}
	for(int i=bid[l]+1;i<=bid[r]-1;i++) {
		if(b[br[i]]+lazy[i]<=d) {
			res+=br[i]-bl[i]+1;
			continue;
		}
		if(b[bl[i]]+lazy[i]>d) {
			continue;
		}
		res+=upper_bound(b+bl[i],b+br[i]+1,d-lazy[i])-b-bl[i];
	}
	return res;
}

int squery(int L,int R,int rank) {
	if(rank<1 || rank>(R-L+1)) {
		return -1;
	}
	int l=minq(L,R),r=maxq(L,R);
	int res=-1;
	while(l<r) {
		int mid=l+((r-l)>>1);
		if(rankq(L,R,mid)<rank) {
			l=mid+1;
		}else {
			res=mid;
			r=mid-1;
		}
	}
	return res;
}

int main() {
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
	}
	block=sqrt(n);
	bcnt=(n+block-1)/block;
	for(int i=1;i<=bcnt;i++) {
		bl[i]=(i-1)*block+1;
		br[i]=(i==bcnt?n:i*block);
		for(int j=bl[i];j<=br[i];j++) {
			bid[j]=i;
			b[j]=a[j];
		}
		sort(b+bl[i],b+br[i]+1);
	}
	for(int i=1;i<=m;i++) {
		int type,l,r,d;
		scanf("%d %d %d %d",&type,&l,&r,&d);
		if(type==1) {
			printf("%d\n",squery(l,r,d));
		}else {
			modify(l,r,d);
		}
	}
	return 0;
}