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

int n, m;
const int maxn = 1e6 + 233;
int cnt[maxn], a[maxn];
int bel[maxn];

struct node{
    int l, r, t, k, id;
    bool operator <(const node &p) const{
        return bel[l] ^ bel[p.l] ? bel[l] < bel[p.l] : (bel[r] ^ bel[p.r] ? bel[r] < bel[p.r] : (t < p.t));
    }
}q[maxn];

typedef pair<int, int> pii;
pii c[maxn];
int block;
int res[maxn];
pii bound[maxn];
int sz;
int ord[maxn];

void add(int x){
    x = a[x];
    int c = cnt[x];
    if(c == 0){
        ord[++sz] = 1;
        bound[1].first++;
        bound[1].second = sz;
    }
    else{
        if(bound[c + 1].first == 0){
            ord[bound[c].second - bound[c].first + 1]++;
            bound[c + 1].second = bound[c].second - bound[c].first + 1;
        }
        else{
            bound[c + 1].second++;
            ord[bound[c + 1].second]++;
        }
        bound[c + 1].first++;
        bound[c].first--;
        if(bound[c].first == 0){
            bound[c].second = 0;
        }
    }
    cnt[x]++; 
}

void del(int x){
    x = a[x];
    int c = cnt[x];
    if(c == 1){
        ord[sz] = 0;
        --sz;
        bound[1].first--;
        if(bound[1].first == 0) bound[1].second = 0;
        else bound[1].second--;
    }
    else{
        ord[bound[c].second]--;
        if(bound[c - 1].first == 0) bound[c - 1].second = bound[c].second;
        bound[c - 1].first++;

        bound[c].first--;
        if(bound[c].first == 0) {
            bound[c].second = 0;
        }
        else bound[c].second--;
        
       
        
    }
    cnt[x]--;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(10);
    cin >> n >> m;
    block = pow(n, 2.0 / 3);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        bel[i] = i / block + 1;
    }

    int qcnt = 0, rcnt = 0;
    for (int i = 1; i <= m; ++i) {
        int op, x, y, k;
        cin >> op >> x >> y;
        if(op == 1){
            cin >> k;
            q[++qcnt] = node{x, y, rcnt, k, qcnt};
        }
        else{
            c[++rcnt] = pii(x, y);
        }
    }
    sort(q + 1, q + qcnt + 1);
    int l = 1, r = 0, t = 0;

    for(int i = 1; i <= m; i++){

        while(t < q[i].t){
            ++t;
            if(c[t].first >= l && c[t].first <= r){
                del(c[t].first);
            }
            swap(a[c[t].first], c[t].second);
            if(c[t].first >= l && c[t].first <= r){
                add(c[t].first);
            }
        }
        while(t > q[i].t){
            if(c[t].first >= l && c[t].first <= r){
                del(c[t].first);
            }
            swap(a[c[t].first], c[t].second);
            if(c[t].first >= l && c[t].first <= r){
                add(c[t].first);
            }
            --t;
        }
        while(l > q[i].l) add(--l);
        while(r < q[i].r) add(++r);
        while(l < q[i].l) del(l++);
        while(r > q[i].r) del(r--);

        

        
        int ans = INT_MAX;
        int all = 0;
        int j = 1;

        /*
        cout << "test: " << q[i].l << " " << q[i].r << "\n";
        for (int t = 1; t <= sz; ++t){
            cout << ord[t] << " ";
        }
        cout << "\n";*/

        for(int o = 1; o <= sz; o = bound[ord[o]].second + 1){
            all += bound[ord[o]].first;
            while(j <= o && all - bound[ord[j]].first >= q[i].k){
                all -= bound[ord[j]].first;
                j = bound[ord[j]].second + 1;
            }
            if(all >= q[i].k) ans = min(ans, ord[j] - ord[o]); 
        }
        if(ans == INT_MAX) ans = -1;
        res[q[i].id] = ans;
    }
    for (int i = 1; i <= qcnt; ++i) {
        cout << res[i] << '\n';
    }
    return 0;
}