#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ll long long
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define ff first
#define ss second
#define ld long double
#define pii pair<int, int>

#define prev prev228
#define left left228
#define right right228
#define dist dist228
#define tm tm228

using namespace std;

mt19937 rnd(time(nullptr));

const long long INF = 1e9, P = 1e9 + 7, N = 1e5 + 10, X = 1500;
const long double EPS = 1e-9;
int n, m, a[N], cnt[N], cur_a[N], arr[N], ans[N], l = 0, r = -1, t = -1;
pair<int, int> seg[N];
vector<vector<int> > to_upd, qr;

void add(int x) {
    int i = seg[cnt[x]].second;
    seg[cnt[x]].second--;
    if (seg[cnt[x]].second - seg[cnt[x]].first + 1 <= 0) {
        seg[cnt[x]] = {-1, -2};
    }
    cnt[x]++;
    arr[i]++;
    if (seg[cnt[x]] == make_pair(-1, -2)) {
        seg[cnt[x]] = {i, i};
    } else {
        seg[cnt[x]].first--;
    }
}

void kick(int x) {
    int i = seg[cnt[x]].first;
    seg[cnt[x]].first++;
    if (seg[cnt[x]].second - seg[cnt[x]].first + 1 <= 0) {
        seg[cnt[x]] = {-1, -2};
    }
    cnt[x]--;
    arr[i]--;
    if (seg[cnt[x]] == make_pair(-1, -2)) {
        seg[cnt[x]] = {i, i};
    } else {
        seg[cnt[x]].second++;
    }
}

int get_ans(int k) {
    int ans = INF, cur = 0, j = n + 1;
    for (int i = seg[arr[n]].first; i >= 0;) {
        if (j > i) {
            j = i;
            cur = seg[arr[i]].second - seg[arr[i]].first + 1;
        }
        while (j - 1 >= 0 && cur < k) {
            j--;
            int val = arr[j], cnt_cnt = seg[val].second - seg[val].first + 1;
            if (val != 0) {
                cur += cnt_cnt;
            }
            j = seg[val].first;
        }
        if (cur >= k) {
            ans = min(ans, abs(arr[i] - arr[j]));
        } else {
            break;
        }
        int val = arr[i], cnt_cnt = seg[val].second - seg[val].first + 1;
        cur -= cnt_cnt;
        if (i == 0) {
            break;
        }
        i = seg[arr[i - 1]].first;
    }
    return (ans == INF ? -1 : ans);
}

void do_upd(int t) {
    int p = to_upd[t][0], old = to_upd[t][1], vl = to_upd[t][2];
    if (l <= p && p <= r) {
        kick(old);
        add(vl);
    }
    a[p] = vl;
}

void roll_back(int t) {
    int p = to_upd[t][0], old = to_upd[t][1], vl = to_upd[t][2];
    if (l <= p && p <= r) {
        kick(vl);
        add(old);
    }
    a[p] = old;
}

bool comp(vector<int> a, vector<int> b) {
    int t1 = a[0] / X, t2 = b[0] / X, l1 = a[1] / X, l2 = b[1] / X, r1 = a[2] / X, r2 = b[2] / X;
    if (t1 == t2) {
        if (l1 == l2) {
            return r1 < r2;
        }
        return l1 < l2;
    }
    return t1 < t2;
}

void print() {
    cout << "===\n";
    cout << "cnt ";
    int Q = 7;
    for (int i = 0; i <= Q; i++) {
        cout << cnt[i] << ' ';
    }
    cout << "\n";
    cout << "seg ";
    for (int i = 0; i <= n; i++) {
        cout << seg[i].first << ' ' << seg[i].second << "| ";
    }
    cout << "\n";
    cout << "b ";
    for (int i = 0; i <= n; i++) {
        cout << arr[i] << ' ';
    }
    cout << "\n";
    cout << "===\n";
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < N; i++) {
        seg[i] = {-1, -2};
    }
    for (int i = 0; i < N; i++) {
        ans[i] = -2;
    }
    seg[0] = {0, n};
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        cur_a[i] = a[i];
    }
    for (int i = 0; i < m; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            int l, r, k;
            cin >> l >> r >> k;
            l--;
            r--;
            qr.push_back({(int)to_upd.size() - 1, l, r, k, i});
        } else {
            int p, x;
            cin >> p >> x;
            p--;
            int old = cur_a[p];
            cur_a[p] = x;
            to_upd.push_back({p, old, x});
        }
    }
    /*add(1);
    add(1);
    add(2);
    add(1);
    add(1);
    kick(1);
    add(2);
    add(2);
    kick(2);
    add(3);
    add(4);
    kick(4);
    print();
    cout << get_ans(7) << "\n";
    return;*/
    sort(all(qr), comp);
    //random_shuffle(all(qr));
    for (vector<int> elem : qr) {
        int nt = elem[0], nl = elem[1], nr = elem[2], k = elem[3], id = elem[4];
        //cout << "nt " << nt << ' ' << "nl " << nl << ' ' << "nr " << nr << ' ' << "k " << k << ' ' << "id " << id << "\n";
        while (t < nt) {
            do_upd(t + 1);
            t++;
        }
        while (t > nt) {
            roll_back(t);
            t--;
        }
        while (l > nl) {
            add(a[l - 1]);
            l--;
        }
        while (r < nr) {
            add(a[r + 1]);
            r++;
        }
        while (l < nl) {
            kick(a[l]);
            l++;
        }
        while (r > nr) {
            kick(a[r]);
            r--;
        }
        //print();
        int cur_ans = get_ans(k);
        //cout << "ans " << cur_ans << "\n";
        ans[id] = cur_ans;
    }
    for (int i = 0; i < m; i++) {
        if (ans[i] == -2) {
            continue;
        } else {
            cout << ans[i] << '\n';
        }
    }
    cout << "\n";
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //cout << setprecision(15) << fixed;

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    solve();
    return 0;
}
