#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int a[N], pos[N], L[N], R[N], tag[N], ll, rr, b[N];

bool check(int l, int r, int k, int mid){
    int ans = 0;
    if(pos[l] == pos[r]){
        for(int i = l; i <= r; i++)
            ans += (a[i] <= mid - tag[pos[i]]);
    }
    else {
        //cout << k << "\n";
        for(int i = pos[l] + 1; i <= pos[r] - 1; i++) ans += upper_bound(b + L[i], b + R[i] + 1, mid - tag[i]) - (b + L[i]);
       // cout << "ans1=" << ans << "\n";
        for(int i = l; i <= R[pos[l]]; i++) ans += (a[i] <= mid - tag[pos[l]]);
        for(int i = L[pos[r]]; i <= r; i++) ans += (a[i] <= mid - tag[pos[r]]);
       // printf("rank : %d, x : %d , goal : %d\n", ans, mid, k);
       // cout << k << " " << ans << "\n";
    }
    
    return ans >= k;
}

int query(int l, int r, int k){
    int lt = ll - 1, rt = rr + 1, mid;
    if(pos[l] == pos[r]) {
        while(lt + 1 < rt){
            mid = lt + rt >> 1;
            if(check(l, r, k, mid) == true) rt = mid;
            else lt = mid;
        }
        return rt;
    }
    else {
        while(lt + 1 < rt){
            mid = lt + rt >> 1;
            if(check(l, r, k, mid) == true) rt = mid;
            else lt = mid;
        }
        return rt;
    }
}

void update(int l, int r, int val){
    if(pos[l] == pos[r]){
        for(int i = L[pos[l]]; i <= R[pos[r]]; i++){
            if(i >= l and i <= r) a[i] += val;
            b[i] = a[i];
        }
        sort(b + L[pos[l]], b + R[pos[l]] + 1);
    }
    else {
        for(int i = pos[l] + 1; i <= pos[r] - 1; i ++) tag[i] += val;
        if(l == L[pos[l]]) tag[pos[l]] += val;
        else { for(int i = L[pos[l]]; i <= R[pos[l]]; i++) { if(i >= l) { a[i] += val; }; b[i] = a[i]; } sort(b + L[pos[l]], b + R[pos[l]] + 1); }
        if(r == R[pos[r]]) tag[pos[r]] += val;
        else { for(int i = L[pos[r]]; i <= R[pos[r]]; i++) { if(i <= r) { a[i] += val; }; b[i] = a[i]; } sort(b + L[pos[r]], b + R[pos[r]] + 1); }
    }
}
#define LOCAL

int main(){
    #ifdef LOCAL
        freopen("in.in", "r", stdin);
        freopen("out.out", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n, m, siz, num; cin >> n >> m; siz = sqrt(n); num = n / siz + (n % siz != 0);
    //cout << siz << "\n"; 
    //memset(Min, 0x7f, sizeof(Min));
    //memset(Max, 0xcf, sizeof(Max));
    for(int i = 1; i <= n; i++){ cin >> a[i]; b[i] = a[i];}
    ll = 1145141919;
    for(int i = 1; i <= num; i++){
        L[i] = (i - 1) * siz + 1, R[i] = i * siz;
        if(i == num) R[i] = n;
        for(int j = L[i]; j <= R[i]; j++){
            pos[j] = i; ll = min(ll, a[j]); rr = max(rr, a[j]);
        }
        sort(b + L[i], b + R[i] + 1);
        //for(int j = L[i]; j <= R[i]; j++) cout << b[j] << " "; 
    }
    //puts("");
    while(m--){
        int opt, l, r, k; cin >> opt >> l >> r >> k;
        if(opt == 1) { if(k > r - l + 1 or k < 1) cout << -1 << "\n"; else cout << query(l, r, k) << "\n"; }
        else { update(l, r, k); if(k > 0) rr += k; else ll += k; /*puts("\n"); for(int i = 1; i <= num; i++) cout << tag[i] << " "; puts("\n");*/}
    }
}

我的块长开到 $\sqrt{n}$

开到$\sqrt{n}\log n$ 这是为啥