#pragma GCC optimize(2)
#pragma GCC optimize(3)

#include <bits/stdc++.h>

using namespace std;

struct fastin {
    template<typename T>
    fastin& operator >> (T &i) {
        int f; auto it = istreambuf_iterator<char>(cin);
        for (f = 1; not isdigit(*it); ++it) if (*it == '-') f = -1;
        for (i = 0; isdigit(*it); ++it) i = i * 10 + *it - '0';
        i *= f; return *this;
    }
} fin;

#define ll long long

constexpr int N = 1e5 + 100;

int cnt[N], a[N], b[N];
int num[N];
int ans[N];

vector<int> big;

int n, m;

struct node {
    int l, r, k, pre, id;
}s[N];

struct star {
    int pos, val;
}op[N];

inline void add(int x) {
    num[cnt[a[x]]] --;
    cnt[a[x]] ++;
    num[cnt[a[x]]] ++;
}

inline void sub(int x) {
    num[cnt[a[x]]] --;
    cnt[a[x]] --;
    num[cnt[a[x]]] ++;
}

inline void work(int x, int l, int r) {
    int numx = op[x].pos;
    if(numx >= l and numx <= r) {
        sub(numx);
        swap(a[numx], op[x].val);
        add(numx);
    } else {
        swap(a[numx], op[x].val);
    }
}


int main() {

    ios::sync_with_stdio(false);

#if ONLINE_JUDGE
#else
    freopen("C:/practice/cpp/data/in.txt", "r", stdin);
    freopen("C:/practice/cpp/data/out.txt", "w", stdout);
#endif

    fin >> n >> m;
    int MAX = sqrt(n), block = pow(n, 2.0 / 3.0);
    for (int i = 1; i <= n; ++i) fin >> a[i], b[a[i]] ++;

    int Cnum = 0, Qnum = 0;
    for(int i = 1; i <= m; ++i) {
        int cmd, l, r, k, id, val;
        fin >> cmd;
        if(cmd == 1) {
            fin >> l >> r >> k;
            ++Qnum;
            s[Qnum] = {l, r, k, Cnum, Qnum};
        } else {
            fin >> id >> val;
            op[++Cnum] = {id, val};
            b[val] ++;
        }
    }

    for (int i = 1; i <= 100000; ++i) if (b[i] > MAX) big.push_back(i);

    sort(s + 1, s + 1 + Qnum, [&](node a, node b) {
        if(a.l / block != b.l / block) return a.l / block < b.l / block;
        if(a.r / block != b.r / block) {
            if (a.l / block & 1) return a.r / block < b.r / block;
            else return a.r / block > b.r / block;
        }
        if ((a.l / block & 1) == (a.r / block & 1)) return a.pre < b.pre;
        return a.pre > b.pre;
    });

    int l = 1, r = 0, now = 0;
    for(int i = 1; i <= Qnum; ++i) {
        while(s[i].l < l) add(--l);
        while(s[i].r > r) add(++r);
        while(s[i].l > l) sub(l++);
        while(s[i].r < r) sub(r--);
        while(now < s[i].pre) work(++now, l, r);
        while(now > s[i].pre) work(now--, l, r);

        vector<pair<int, int> > v;
        for (int j = 1; j <= MAX; ++j) {
            if (num[j] > 0) v.emplace_back(j, num[j]);
        }

        vector<int> e;
        for (int j = 0, len = big.size(); j < len; ++j) {
            if (cnt[big[j]] > MAX) e.emplace_back(cnt[big[j]]);
        }

        sort(e.begin(), e.end());
        for (int j = 0, len = e.size(); j < len; ++j) {
            int pre = j;
            while (j + 1 < len and e[j] == e[j + 1]) ++j;
            v.emplace_back(e[j], j - pre + 1);
        }

        int pre = 0, last = -1, len = v.size();
        int sum = 0, val = n;
        while (pre < len) {
            while (sum < s[i].k and last + 1 < len) sum += v[++last].second;
            if (sum < s[i].k) break;
            val = min(val, v[last].first - v[pre].first);
            sum -= v[pre++].second;
        }
        ans[s[i].id] = val;
    }

    for (int i = 1; i <= Qnum; ++i) {
        if (ans[i] == n) cout << "-1\n";
        else cout << ans[i] << '\n';
    }
}