RT

sub#1 WA4个点，剩下TLE

sub#2 AC

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll MAXN=1e5+5;
ll n,m;
int op,x,y,z,blen;
struct block{
	int b_l,b_r;
	ll lazy_add;
}b[MAXN];
int b_id[MAXN];
int cnt;
struct node{
	ll num;
	int id;
	bool operator == (const node &oth)const{
		return num==oth.num;
	}
}a[MAXN],tmp[MAXN];
bool cmp_num(node n1,node n2){
	return n1.num<n2.num;
}
bool cmp_id(node n1,node n2){
	return n1.id<n2.id;
}
int count(int L,int R,ll X){
	if(X>=a[R].num)return R-L+1;
	if(X<a[L].num)return 0;
	int res=upper_bound(a+L,a+R+1,(node){X,0},cmp_num)-a-1;
    return res;
}
void sort_id(int L,int R){
	for(int i=L;i<=R;i++)tmp[a[i].id]=a[i];
	for(int i=L;i<=R;i++)a[i]=tmp[i];
	return;
}
int read(){
   int s = 0,w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
   while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
   return s * w;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		a[i].num=read();
		a[i].id=i;
	}
	blen=70;
	for(int i=1;i<=n;i+=blen)b[++cnt]=(block){i,min(i+blen-1ll,n*1ll),0};
	for(int i=1;i<=cnt;i++)for(int j=b[i].b_l;j<=b[i].b_r;j++)b_id[j]=i;
	for(int i=1;i<=cnt;i++)sort(a+b[i].b_l,a+b[i].b_r+1,cmp_num);
    for(int i=1;i<=m;i++){
        op=read(),x=read(),y=read(),z=read();
        if(op==2){
            if(b_id[x]==b_id[y]){
                sort_id(b[b_id[x]].b_l,b[b_id[x]].b_r);
                for(int i=x;i<=y;i++)a[i].num+=z;
                sort(a+b[b_id[x]].b_l,a+b[b_id[x]].b_r+1,cmp_num);
            }
            else{
                for(int i=b_id[x]+1;i<b_id[y];i++)b[i].lazy_add+=z;
                sort_id(b[b_id[x]].b_l,b[b_id[x]].b_r);
                for(int i=x;i<=b[b_id[x]].b_r;i++)a[i].num+=z;
                stable_sort(a+b[b_id[x]].b_l,a+b[b_id[x]].b_r+1,cmp_num);
                sort_id(b[b_id[y]].b_l,b[b_id[y]].b_r);
                for(int i=b[b_id[y]].b_l;i<=y;i++)a[i].num+=z;
                stable_sort(a+b[b_id[y]].b_l,a+b[b_id[y]].b_r+1,cmp_num);
            }
        }
        else{
            if(b_id[x]==b_id[y]){
                sort_id(b[b_id[x]].b_l,b[b_id[x]].b_r);
                cout<<a[x+z-1].num+b[b_id[x]].lazy_add<<'\n';
                stable_sort(a+b[b_id[x]].b_l,a+b[b_id[x]].b_r+1,cmp_num);
                continue;
            }
            ll L=4e13,R=-4e13,mid=0,ans=0;
            for(int i=b_id[x];i<=b_id[y];i++)L=min(L,a[b[i].b_l].num+b[i].lazy_add),R=max(R,a[b[i].b_r].num+b[i].lazy_add);
            while(L<=R){
                mid=(L+R)>>1;
                ll s=0;
                for(int i=b_id[x]+1;i<b_id[y];i++)s+=count(b[i].b_l,b[i].b_r,mid-b[i].lazy_add);
                sort_id(b[b_id[x]].b_l,b[b_id[x]].b_r);
                for(int i=x;i<=b[b_id[x]].b_r;i++)s+=(a[i].num+b[b_id[x]].lazy_add<=mid);
                stable_sort(a+b[b_id[x]].b_l,a+b[b_id[x]].b_r+1,cmp_num);
                sort_id(b[b_id[y]].b_l,b[b_id[y]].b_r);
                for(int i=b[b_id[y]].b_l;i<=y;i++)s+=(a[i].num+b[b_id[y]].lazy_add<=mid);
                stable_sort(a+b[b_id[y]].b_l,a+b[b_id[y]].b_r+1,cmp_num);
                if(s<z)L=mid+1;
                else R=mid-1,ans=mid;
            }
            cout<<ans<<'\n';
        }
    }
	return 0;
}