#include<bits/stdc++.h>
#define INF 0x7f7f7f7f
#define up(i,a,b) for(int i=a;i<=b;i++)
#define down(i,a,b) for(int i=a;i>=b;i--)
#define mem(a,v) memset(a,v,sizeof(a))
#define int long long
using namespace std;
const int MAXN = 1e6 + 7;
inline int read(){
	int x=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
inline void write(int x){
	if(x>9)write(x/10);
	putchar(48+x%10);
}
int N, Q, t, block;
int a[MAXN];
int st[MAXN], ed[MAXN], pos[MAXN];
int b[MAXN], add[MAXN], mx[MAXN], mn[MAXN];
void change(int l, int r, int W){
	int p = pos[l], q = pos[r];
	if(p == q){
		up(i, l, r)a[i] += W;
		up(i, st[p], ed[p])b[i] = a[i];
		sort(b + st[p], b + ed[p] + 1);
	}
	else{
		up(i, p+1, q-1)add[i] += W;
		up(i, l, ed[p])a[i] += W;
		up(i, st[p], ed[p])b[i] = a[i];
		sort(b+st[p],b+ed[p]+1);	
		up(i, st[q], r)a[i] += W;
		up(i, st[q], ed[q])b[i] = a[i];
		sort(b+st[q],b+ed[q]+1);	
	}
}
int qcnt(int l, int r, int c){
	int p = pos[l], q = pos[r], cnt = 0;
	if(p == q){
		up(i, l, r)if(a[i] + add[p] <= c)cnt++;
	}
	else{
		up(i, p+1, q-1){
			int val = (upper_bound(b + st[i], b + ed[i] + 1, c - add[i]) - b)-st[i] ;
			cnt += val;
		}
		up(i, l, ed[p])if(a[i] + add[p] <= c)cnt++;
		up(i, st[q], r)if(a[i] + add[q] <= c)cnt++;
	}	
	return cnt;
}
int qmax(int l, int r){
	int p = pos[l], q = pos[r], ans = -INF;
	if(p == q){
		up(i, l, r){
			ans = max(ans, a[i] + add[p]);
		}
	}
	else{
		up(i, p+1, q-1)ans = max(ans, mx[i] + add[i]);
		up(i, l, ed[p])ans = max(ans, a[i] + add[p]);
		up(i, st[q], r)ans = max(ans, a[i] + add[q]);
	}
	return ans;	
}
int qmin(int l, int r){
	int p = pos[l], q = pos[r], ans = INF;
	if(p == q){
		up(i, l, r){
			ans = min(ans, a[i] + add[p]);
		}
	}
	else{
		up(i, p+1, q-1)ans = min(ans, mn[i] + add[i]);
		up(i, l, ed[p])ans = min(ans, a[i] + add[p]);
		up(i, st[q], r)ans = min(ans, a[i] + add[q]);
	}	
	return ans;
}
int query(int L, int R, int k){
	if(k<1||k>R-L+1)return 1;
	if(k==1)return qmin(L, R);
	if(k==R-L+1)return qmax(L, R);
	int l = qmin(L, R), r = qmax(L, R);
	int ans =l;
	while(l <= r){
		int mid = (l + r)>>1;
		if(qcnt(L, R, mid) <= k){
			l = mid + 1, ans = mid;
		}
		else r = mid - 1;
	}
	
	return ans;
}
signed main(){
	//freopen("Ynoi.in","r",stdin);
	//freopen("fk.out","w",stdout);
	N = read(), Q = read();
	up(i, 1, N) a[i] = read(), b[i] = a[i];
	block = sqrt(N);
	t = N/block;
	if(N % block)t++;
	up(i, 1, t){
		st[i] = (i-1) * block + 1;
		ed[i] = i * block;
		sort(b + st[i], b + ed[i] + 1);
	}
	ed[t] = N;
	up(i, 1, t){
		mx[i] = a[st[i]];
		mn[i] = a[st[i]];
		up(j, st[i], ed[i]){
			mx[i] = max(mx[i], a[j]);
			mn[i] = min(mn[i], a[j]);
		}
	}
	up(i, 1, N) pos[i] = (i - 1)/block + 1;
	while(Q--){
		int opt = read();
		if(opt == 2){
			int L = read();
			int R = read();
			int W = read();
			change(L, R, W);
		}
		else {
			int L = read();
			int R = read();
			int k = read();
			printf("%lld\n",query(L, R, k));
		}
	}
	return 0;
}

记录