后面的 hack 数据都过了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace fast_IO {
#define IOSIZE 100000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
const int N=2e5+10;
const int INF=0x3f3f3f3f3f3f3f3f;
int n,q,a[N],b[N];
int l[N],r[N],bel[N],add[N];
int S,loc;
inline void init() {
	for (int i=1;i<=n;i++) cin>>a[i],b[i]=a[i],bel[i]=(i-1)/S+1;
	for (int i=1;i<=loc;i++) l[i]=(i-1)*S+1,r[i]=i*S;r[loc]=n;
	for (int i=1;i<=loc;i++) sort(b+l[i],b+r[i]+1);
	return ;
}
inline void modify(int ls,int rs,int blo,int x) {
	for (int i=ls;i<=rs;i++) a[i]+=x;
	for (int i=l[blo];i<=r[blo];i++) b[i]=a[i];
	sort(b+l[blo],b+r[blo]+1);
	return ;
}
inline void update(int ls,int rs,int x) {
	int bll=bel[ls],blr=bel[rs];
	if (bll==blr) {
		modify(ls,rs,bll,x);
		return ;
	}
	modify(ls,r[bll],bll,x);
	modify(l[blr],rs,blr,x);
	for (int i=bll+1;i<=blr-1;i++) add[i]+=x;
	return ;
}
inline int check(int ls,int rs,int k) {
	int bll=bel[ls],blr=bel[rs],res=0;
	if (bll==blr) {
		for (int i=ls;i<=rs;i++) 
			if (a[i]+add[bll]<=k) 
				res++;
		return res;
	}
	for (int i=ls;i<=r[bll];i++) 
		if (a[i]+add[bll]<=k)
			res++;
	for (int i=l[blr];i<=rs;i++)
		if (a[i]+add[blr]<=k)
			res++;
	for (int i=bll+1;i<=blr-1;i++) {
		int R=l[i],L=r[i];
		if (add[i]+b[l[i]]>k) continue;
		if (add[i]+b[r[i]]<=k) {
			res+=(r[i]-l[i]+1);
			continue;
		}
		while (L<R) {
			int mid=(L+R>>1)+1;
			if (b[mid]+add[i]<=k) L=mid;
			else R=mid-1;
		}
		if (b[L]+add[i]<=k) res+=(L-l[i]+1);
	}
	return res;
}
inline int maxx(int ls,int rs) {
	int bll=bel[ls],blr=bel[rs],mx=-INF;
	if (bll==blr) {
		for (int i=ls;i<=rs;i++) mx=max(mx,a[i]);
		return mx;
	}
	for (int i=ls;i<=r[bll];i++) mx=max(mx,a[i]);
	for (int i=l[blr];i<=rs;i++) mx=max(mx,a[i]);
	for (int i=bll+1;i<=blr-1;i++) mx=max(mx,b[r[i]]);
	return mx;
}
inline int minn(int ls,int rs) {
	int bll=bel[ls],blr=bel[rs],mn=INF;
	if (bll==blr) {
		for (int i=ls;i<=rs;i++) mn=min(mn,a[i]); 	
		return mn;
	}
	for (int i=ls;i<=r[bll];i++) mn=min(mn,a[i]);
	for (int i=l[blr];i<=rs;i++) mn=min(mn,a[i]);
	for (int i=bll+1;i<=blr-1;i++) mn=min(mn,b[l[i]]);
	return mn;
}
inline int query(int ls,int rs,int k) {
	if (k<1 or k>rs-ls+1) return -1;
	int L=minn(ls,rs),R=maxx(ls,rs),ans=-1;
	while (L<=R) {
		int mid=L+R>>1;
		if (check(ls,rs,mid)<k) L=mid+1;
		else R=mid-1,ans=mid;
	}
	return ans;
}
signed main() {
	cin>>n>>q;S=sqrt(n);
	loc=(n-1)/S+1;
	init();
	while (q--) {
		int op,ls,rs,k;
		cin>>op>>ls>>rs>>k;
		if (op==2) update(ls,rs,k);
		else cout<<query(ls,rs,k)<<endl;
	}
	return (0-0);
}