首先做区间加区间 $< x$ :
分块，块内维护 OV。
​ 区间加时对块打 tag，块内相对大小不变。散块暴力重构，归并加的序列和每加的序列。
​ 块长 $\mathcal{O}(\sqrt{n \log n})$ ，复杂度 $\mathcal{O}(m \sqrt{n \log n})$ 。

然后，区间加区间 $k$ th:
直接二分然后用上面的东西判断是 $\mathcal{O}(m \sqrt{n \log n} \log n)$ 的。
​ 观察零散块查询的暴力是 $\mathcal{O}(x \log n)$ ，整块的查询是 $\mathcal{O}(\frac{n}{x} \log ^2 n)$ 的。
​ 零散块的暴力显然可以优化，预先排序（归并）之后二分查询，复杂度是 $\mathcal{O}(x + \log^2n)$ 的。
​ 这样平衡就变成了 $x \sim \frac{n}{x} \log^2 n$ 。取块长 $\sqrt n \log n$ ，复杂度 $\mathcal{O}(m \sqrt n \log n)$ 。

const int maxn = 1e5, bs = 2.5e3, nb = maxn / bs + 1;
#define blk(x) (((x)-1)/bs)
#define hob(x) ((x)*bs+1)
#define eob(x) min(((x)+1)*bs,n)
int a[maxn + 10];
int ovi[maxn + 10], tag[nb + 10], buf1[bs + 10], buf2[bs + 10], n;
int tmp[bs * 2 + 10], ed;

void add(int l, int r, int c) {
    int lb = blk(l), rb = blk(r);
    if(lb == rb) {
        rep(i,l,r) a[i] += c;
        // merge sort O(x)
        int e1 = -1, e2 = -1, p1 = 0, p2 = 0;
        rep(i,hob(lb),eob(lb))
            if(ovi[i] >= l && ovi[i] <= r) buf1[++ e1] = ovi[i];
            else buf2[++ e2] = ovi[i];
        rep(i,hob(lb),eob(lb))
            if(p2 > e2 || p1 <= e1 && a[buf1[p1]] < a[buf2[p2]]) ovi[i] = buf1[p1 ++];
            else ovi[i] = buf2[p2 ++];

        return ;
    }
    rep(i,lb + 1, rb - 1) tag[i] += c;
    rep(i,l,eob(lb)) a[i] += c;
    rep(i,hob(rb),r) a[i] += c;
    // merge sort O(x)
    int e1 = -1, e2 = -1, p1 = 0, p2 = 0;
    rep(i,hob(lb),eob(lb))
        if(ovi[i] >= l && ovi[i] <= r) buf1[++ e1] = ovi[i];
        else buf2[++ e2] = ovi[i];
    rep(i,hob(lb),eob(lb))
        if(p2 > e2 || p1 <= e1 && a[buf1[p1]] < a[buf2[p2]]) ovi[i] = buf1[p1 ++];
        else ovi[i] = buf2[p2 ++];
    // merge sort O(x)
    e1 = e2 = -1, p1 = p2 = 0;
    rep(i,hob(rb),eob(rb))
        if(ovi[i] >= l && ovi[i] <= r) buf1[++ e1] = ovi[i];
        else buf2[++ e2] = ovi[i];
    rep(i,hob(rb),eob(rb))
        if(p2 > e2 || p1 <= e1 && a[buf1[p1]] < a[buf2[p2]]) ovi[i] = buf1[p1 ++];
        else ovi[i] = buf2[p2 ++];

}

void prework(int l, int r) {
    int lb = blk(l), rb = blk(r);
    int e1 = -1, e2 = -1, p1 = 0, p2 = 0;
    ed = -1;
    if(lb == rb) {
        rep(i,hob(lb),eob(rb)) if(ovi[i] >= l && ovi[i] <= r) tmp[++ ed] = ovi[i];
    } else {
        rep(i,hob(lb),eob(lb)) if(ovi[i] >= l && ovi[i] <= r) buf1[++ e1] = ovi[i];
        rep(i,hob(rb),eob(rb)) if(ovi[i] >= l && ovi[i] <= r) buf2[++ e2] = ovi[i];

        while(p1 <= e1 || p2 <= e2) {
            if(p2 > e2 || p1 <= e1 && a[buf1[p1]] + tag[lb] < a[buf2[p2]] + tag[rb]) tmp[++ ed] = buf1[p1 ++];
            else tmp[++ ed] = buf2[p2 ++];
        }
    }
}

int calc(int l, int r, int c) {
    // \sum [a[i]] < c * c
    int lb = blk(l), rb = blk(r);
    int ans = 0;
    rep(i, lb + 1, rb - 1) {
        int l = hob(i), r = eob(i);
        if(a[ovi[l]] + tag[i] >= c) continue;
        while(l < r) {
            int mid = (l + r + 1) >> 1;
            if(a[ovi[mid]] + tag[i] < c) l = mid;
            else r = mid - 1;
        }
        ans += l - hob(i) + 1;
    }
    if(~ed && a[tmp[0]] + tag[blk(tmp[0])] < c) {
        int l = 0, r = ed;
        while(l < r) {
            int mid = (l + r + 1) >> 1;
            if(a[tmp[mid]] + tag[blk(tmp[mid])] < c) l = mid;
            else r = mid - 1;
        }
        ans += l + 1;
    }
    return ans;
}

int main() {
    int m;
    scanf("%d %d", &n, &m);
    rep(i,1,n) scanf("%d", a + i), ovi[i] = i;
    rep(i,blk(1),blk(n)) sort(ovi + hob(i), ovi + eob(i) + 1, [&](int x, int y) { return a[x] < a[y]; });
    int opt, l, r;
    int c;
    rep(qr,1,m) {
        scanf("%d %d %d %d", &opt, &l, &r, &c);
        if(opt == 2) {
            add(l, r, c);
        } else {
            if(c > r - l + 1) putchar('-'), putchar('1'), putchar('\n');
            else {
                int rl = -2e9, rr = 2e9;
                prework(l, r);
                while(rl < rr) {
                    int rmid = (rl + rr + 1) >> 1;
                    if(calc(l, r, rmid) <= c - 1) rl = rmid;
                    else rr = rmid - 1;
                }
                printf("%d\n", rl);
            }
        }
    }
    return 0;
}