/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100002;
const int M_MAX = 100002;
const int A_MAX = 100002;

const int A = 100000;

int n, m;

int arr[N_MAX];

int bucketSize;

struct Query
{
    int l, r, k;
    int cntUpdates;
    int index;
};

bool operator < (const Query &a, const Query &b)
{
    return make_pair(make_pair((a.l - 1) / bucketSize, (a.r - 1) / bucketSize), a.cntUpdates)
         < make_pair(make_pair((b.l - 1) / bucketSize, (b.r - 1) / bucketSize), b.cntUpdates);
}

int aux[N_MAX];

struct Update
{
    int pos, oldval, newval;
};

vector <Query> queries;
vector <Update> updates;

int answer[M_MAX];

int freq[A_MAX];

int sortedFreq[A_MAX];

int firstOcc[N_MAX], lastOcc[N_MAX], cntOcc[N_MAX];

void insertValue (int val)
{
    sortedFreq[lastOcc[freq[val]]]++;
    cntOcc[freq[val]]--;
    cntOcc[freq[val] + 1]++;
    firstOcc[freq[val] + 1] = lastOcc[freq[val]];
    lastOcc[freq[val]]--;
    if(cntOcc[freq[val] + 1] == 1)
        lastOcc[freq[val] + 1] = firstOcc[freq[val] + 1];
    freq[val]++;
}

void eraseValue (int val)
{
    sortedFreq[firstOcc[freq[val]]]--;
    cntOcc[freq[val]]--;
    cntOcc[freq[val] - 1]++;
    lastOcc[freq[val] - 1] = firstOcc[freq[val]];
    firstOcc[freq[val]]++;
    if(cntOcc[freq[val] - 1] == 1)
        firstOcc[freq[val] - 1] = lastOcc[freq[val] - 1];
    freq[val]--;
}

int getAnswer (int k)
{
    int ans = INT_MAX;
    for(int i = 1; i <= A; i++)
    {
        i = lastOcc[sortedFreq[i]];
        if(i - k + 1 >= 1 && sortedFreq[i - k + 1] > 0)
            ans = min(ans, sortedFreq[i] - sortedFreq[i - k + 1]);
    }
    if(ans == INT_MAX)
        ans = -1;
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> arr[i];
    bucketSize = pow(2.0 * n * n, 1.0 / 3.0);
    for(int i = 1; i <= n; i++)
        aux[i] = arr[i];
    for(int i = 1; i <= m; i++)
    {
        int type;
        cin >> type;
        if(type == 1)
        {
            int l, r, k;
            cin >> l >> r >> k;
            queries.push_back(Query{l, r, k, (int)updates.size(), (int)queries.size() + 1});
        }
        else
        {
            int pos, newval;
            cin >> pos >> newval;
            updates.push_back(Update{pos, aux[pos], newval});
            aux[pos] = newval;
        }
    }
    sort(queries.begin(), queries.end());
    int l = 1, r = 0, cntUpdates = 0;
    cntOcc[0] = A;
    firstOcc[0] = 1;
    lastOcc[0] = A;
    for(Query q : queries)
    {
        while(q.l < l)
        {
            l--;
            insertValue(arr[l]);
        }
        while(r < q.r)
        {
            r++;
            insertValue(arr[r]);
        }
        while(l < q.l)
        {
            eraseValue(arr[l]);
            l++;
        }
        while(q.r < r)
        {
            eraseValue(arr[r]);
            r--;
        }
        while(cntUpdates < q.cntUpdates)
        {
            cntUpdates++;
            Update u = updates[cntUpdates - 1];
            if(l <= u.pos && u.pos <= r)
            {
                eraseValue(u.oldval);
                insertValue(u.newval);
            }
            arr[u.pos] = u.newval;
        }
        while(q.cntUpdates < cntUpdates)
        {
            Update u = updates[cntUpdates - 1];
            if(l <= u.pos && u.pos <= r)
            {
                eraseValue(u.newval);
                insertValue(u.oldval);
            }
            arr[u.pos] = u.oldval;
            cntUpdates--;
        }
        answer[q.index] = getAnswer(q.k);
    }
    for(int i = 1; i <= (int)queries.size(); i++)
        cout << answer[i] << "\n";
    return 0;
}
