// In the name of Allah.
// We're nothing and you're everything.
// Ya Ali!

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 14, S = 2000;
struct Block {
    int val, cnt;
};

struct BlockManager {
    list<Block> l{{0, maxn}};
    int cnt[maxn];
    list<Block>::iterator where[maxn];

    BlockManager() {
        where[0] = l.begin();
        fill(where + 1, where + maxn, l.end());
    }

    void add(int x) {
        int &c = cnt[x];
        if (where[c + 1] == l.end())
            where[c + 1] = l.insert(next(where[c]), {c + 1, 0});
        if (!--where[c]->cnt) {
            l.erase(where[c]);
            where[c] = l.end();
        }
        where[++c]->cnt++;
    }

    void remove(int x) {
        int &c = cnt[x];
        if (where[c - 1] == l.end())
            where[c - 1] = l.insert(where[c], {c - 1, 0});
        if (!--where[c]->cnt) {
            l.erase(where[c]);
            where[c] = l.end();
        }
        where[--c]->cnt++;
    }

    int get_ans(int k) {
        int ans = maxn;
        int seen = 0;
        for (auto it = next(l.begin()), jt = it; seen >= k or jt != l.end(); it++) {
            while (jt != l.end() and seen < k)
                seen += jt++->cnt;
            if (seen >= k)
                ans = min(ans, prev(jt)->val - it->val);
            seen -= it->cnt;
        }
        return ans == maxn ? -1 : ans;
    }
} block_manager;

struct Query {
    int t, l, r, k, i;

    array<int, 3> rank() const {
        return {t / S, (t / S % 2 ? -l : l) / S, l / S % 2 ? r : -r};
    }
} queries[maxn];

struct UpdQuery {
    int p, was, x;
};
int n, m, a[maxn], ans[maxn];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    vector<UpdQuery> updates;
    int q = 0;
    for (int i = 0; i < m; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            cin >> queries[q].l >> queries[q].r >> queries[q].k;
            queries[q].l--;
            queries[q].t = updates.size();
            queries[q].i = q;
            q++;
        }
        else {
            int p, x;
            cin >> p >> x;
            p--;
            updates.push_back({p, a[p], x});
            a[p] = x;
        }
    }
    sort(queries, queries + q, [](Query &a, Query &b) { return a.rank() < b.rank(); });
    int l = 0, r = 0, t = updates.size();
    for_each(queries, queries + q, [&](Query q) {
        while (l > q.l)
            block_manager.add(a[--l]);
        while (r < q.r)
            block_manager.add(a[r++]);
        while (r > q.r)
            block_manager.remove(a[--r]);
        while (l < q.l)
            block_manager.remove(a[l++]);
        while (t > q.t) {
            t--;
            a[updates[t].p] = updates[t].was;
            if (l <= updates[t].p and updates[t].p < r) {
                block_manager.add(updates[t].was);
                block_manager.remove(updates[t].x);
            }
        }
        while (t < q.t) {
            a[updates[t].p] = updates[t].x;
            if (l <= updates[t].p and updates[t].p < r) {
                block_manager.add(updates[t].x);
                block_manager.remove(updates[t].was);
            }
            t++;
        }
        ans[q.i] = block_manager.get_ans(q.k);
    });
    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';
}
