#include <bits/stdc++.h>
using namespace std;

#define ll int64_t

const int M = 1e5 + 10;

struct Query
{
    int l, r, t, id, k;
};
vector<int> nxt(M), pre(M), tot(M);
vector<int> cnt(M);
vector<int> a;
int res = 0;

void add(int x)
{
    int pt = cnt[x], nt = cnt[x] + 1;
    if (--tot[pt] == 0)
    {
        nxt[pre[pt]] = nxt[pt];
        pre[nxt[pt]] = pre[pt];
        pt = pre[pt];
    }
    cnt[x]++;
    res += (cnt[x] == 1);

    if (tot[nt]++ == 0)
    {
        pre[nt] = pt;
        nxt[nt] = nxt[pt];
        pre[nxt[pt]] = nt;
        nxt[pt] = nt;
    }
};
void del(int x)
{
    int nt = cnt[x], pt = cnt[x] - 1;
    if (--tot[nt] == 0)
    {
        nxt[pre[nt]] = nxt[nt];
        pre[nxt[nt]] = pre[nt];
        nt = nxt[nt];
    }
    res -= (cnt[x] == 1);
    cnt[x]--;

    if (tot[pt]++ == 0)
    {
        nxt[pt] = nt;
        pre[pt] = pre[nt];
        nxt[pre[nt]] = pt;
        pre[nt] = pt;
    }
};
void work(pair<int, int> &now, Query tmp)
{
    auto &[i, c] = now;
    if (tmp.l <= i && i <= tmp.r)
    {
        del(a[i]);
        add(c);
    }
    swap(c, a[i]);
};
void solve()
{
    int n, m;
    cin >> n >> m;
    a = vector<int>(n + 1);

    int B = pow(n, 0.66666666666666);
    int now = -1;

    vector<Query> ask;
    vector<pair<int, int>> cg;

    int head;
    tot[0] = n + 1;
    nxt[0] = n + 1;
    pre[n + 1] = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= m; i++)
    {
        int op, l, r, k;
        cin >> op >> l >> r;
        if (op == 1)
        {
            cin >> k;
            ask.push_back({l, r, (int)cg.size() - 1, (int)ask.size(), k});
        }
        else
            cg.push_back({l, r});
    }

    auto query = [&](int k) {
        int i = nxt[0], j = nxt[0], ans = n + 1, s = 0, cnt = 0;
        if (res < k)
            return -1;
        while (i != n + 1)
        {
            while (j != n + 1 && s < k)
            {
                s += tot[j];
                j = nxt[j];
            }
            if (s >= k)
                ans = min(ans, pre[j] - i);
            s -= tot[i], i = nxt[i];
        }
        return ans;
    };
    sort(ask.begin(), ask.end(), [&](Query x, Query y) { return x.l / B == y.l / B ? (x.r / B == y.r / B ? x.t < y.t : x.r / B < y.r / B) : x.l / B < y.l / B; });
    int li = 1, ri = 0;
    vector<int> ans(ask.size());
    for (auto [l, r, t, id, k] : ask)
    {

        while (li > l)
            add(a[--li]);
        while (ri < r)
            add(a[++ri]);
        while (li < l)
            del(a[li++]);
        while (ri > r)
            del(a[ri--]);
        while (now < t)
            work(cg[++now], {l, r, t, id});
        while (now > t)
            work(cg[now--], {l, r, t, id});
        // cout << l << " " << r << " " << t << endl;
        ans[id] = query(k);
    }
    for (int i : ans)
        cout << i << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;

    while (T--)
    {
        solve();
    }
}