#include<bits/stdc++.h>
#define int long long
#define p pair<int, int>
#define endl '\n'
const int INF = 1000000001;

using namespace std;

struct Mo{
    vector<int> num, light, vertex;
    vector<bool> wow;
    int C, sqrt1;

    Mo(int C_, int sqrt1_){
        C = C_, sqrt1 = sqrt1_;
        num.assign(C, 0);
        wow.assign(C, false);
        light.assign(sqrt1, 0);
    }

    void add(int x){
        if (num[x] < sqrt1){
            light[num[x]]--;
        }
        num[x]++;
        if (num[x] < sqrt1){
            light[num[x]]++;
        }else if (!wow[x]){
            wow[x] = true;
            vertex.push_back(x);
        }
    }

    void del(int x){
        if (num[x] < sqrt1){
            light[num[x]]--;
        }
        num[x]--;
        if (num[x] < sqrt1){
            light[num[x]]++;
        }else if (!wow[x]){
            wow[x] = true;
            vertex.push_back(x);
        }
    }

    int ans(int k){
        vector<int> heavy, vertex1;
        for (int q: vertex){
            if (num[q] < sqrt1){
                wow[q] = false;
            }else{
                vertex1.push_back(q);
                heavy.push_back(num[q]);
            }
        }
        vertex = vertex1;
        sort(heavy.begin(), heavy.end());
        int answer = INF;
        for (int q = (int)heavy.size()-1; q >= k-1; q--){
            answer = min(answer, heavy[q]-heavy[q-k+1]);
        }
        int x = sqrt1-1, sum1 = min((int)heavy.size(), k-1);
        for (int q = sum1-1; q > -1; q--){
            while (x > 0 && sum1+light[x] < k){
                sum1 += light[x];
                x--;
            }
            if (x != 0){
                answer = min(answer, heavy[q]-x);
            }
            sum1--;
        }
        x = 1, sum1 = 0;
        for (int q = 1; q < sqrt1; q++){
            while (x < sqrt1 && sum1+light[x] < k){
                sum1 += light[x];
                x++;
            }
            if (x < sqrt1){
                answer = min(answer, x-q);
                sum1 -= light[q];
            }
        }
        return answer;
    }
};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m, max1 = 1, C = 2500, sqrt1 = 300;
    cin >> n >> m;
    vector<int> a(n), a1(n);
    for (int q = 0; q < n; q++){
        cin >> a[q];
        max1 = max(max1, a[q]+1), a1[q] = a[q];
    }
    vector<pair<p, p>> quest;
    vector<pair<int, p>> change(m, {-1, {-1, -1}});
    for (int q = 0; q < m; q++){
        int type;
        cin >> type;
        if (type == 1){
            int l, r, k;
            cin >> l >> r >> k;
            l--;
            quest.push_back({{l, r}, {q, k}});
        }else{
            int x, y;
            cin >> x >> y;
            x--;
            change[q] = {x, {a1[x], y}};
            a1[x] = y;
        }
    }
    sort(quest.begin(), quest.end(), [C](pair<p, p> x, pair<p, p> y){return x.second.first/C < y.second.first/C || (x.second.first/C == y.second.first/C && (x.first.first/C < y.first.first/C || (x.first.first/C == y.first.first/C && x.first.second < y.first.second)));});
    int l = 0, r = 0, k = 0;
    Mo mo = Mo(max(max1, n+1), sqrt1);
    vector<int> ans(m, -1);
    for (int q = 0; q < quest.size(); q++){
        while (k < quest[q].second.first){
            if (change[k] != pair<int, p>(-1, p(-1, -1))){
                if (l <= change[k].first && change[k].first < r) {
                    mo.del(change[k].second.first);
                    mo.add(change[k].second.second);
                }
                a[change[k].first] = change[k].second.second;
            }
            k++;
        }
        while (k > quest[q].second.first){
            k--;
            if (change[k] != pair<int, p>(-1, p(-1, -1))){
                if (l <= change[k].first && change[k].first < r) {
                    mo.del(change[k].second.second);
                    mo.add(change[k].second.first);
                }
                a[change[k].first] = change[k].second.first;
            }
        }
        while (l > quest[q].first.first){
            l--;
            mo.add(a[l]);
        }
        while (r < quest[q].first.second){
            mo.add(a[r]);
            r++;
        }
        while (l < quest[q].first.first){
            mo.del(a[l]);
            l++;
        }
        while (r > quest[q].first.second){
            r--;
            mo.del(a[r]);
        }
        ans[quest[q].second.first] = mo.ans(quest[q].second.second);
    }
    for (int q = 0; q < m; q++){
        if (ans[q] != -1){
            cout << (ans[q] == INF ? -1 : ans[q]) << endl;
        }
    }
    return 0;
}
