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

const int N = 1e5 + 5;

int n, m, cntm, cntq, bl, a[N], x[N], y[N], cnt[N], lef[N], rit[N], ord[N], ans[N];

struct Query {
  int id, l, r, k, t; 
  inline friend bool operator < (const Query& a, const Query& b) {
    if (a.l / bl != b.l / bl) return a.l < b.l;
    if (a.r / bl != b.r / bl) return a.r < b.r;
    if ((a.r / bl) & 1) return a.t < b.t;
    return a.t > b.t;
  }
} q[N];

void add(int x) {
  --rit[cnt[x]++];
  ord[--lef[cnt[x]]] = cnt[x];
}

void del(int x) {
  ++lef[cnt[x]--];
  ord[++rit[cnt[x]]] = cnt[x];
}

void apply(int tim, int L, int R) {
  if (L <= x[tim] && x[tim] <= R) {
    del(a[x[tim]]);
    add(y[tim]);
  }
  swap(a[x[tim]], y[tim]);
}

int main() {
  scanf("%d%d", &n, &m), bl = pow(n, 2.0 / 3) * 3;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= m; i++) {
    int op;
    scanf("%d", &op);
    if (op == 1) {
      q[++cntq].id = cntq, q[cntq].t = cntm;
      scanf("%d%d%d", &q[cntq].l, &q[cntq].r, &q[cntq].k);
    } else {
      ++cntm;
      scanf("%d%d", &x[cntm], &y[cntm]);
    }
  }
  sort(q + 1, q + cntq + 1);
  int L = 1, R = 0, tim = 0;
  lef[0] = 1, rit[0] = n;
  for (int i = 1; i <= n; i++) lef[i] = n + 1, rit[i] = n;
  for (int i = 1; i <= cntq; i++) {
    while (L > q[i].l) add(a[--L]);
    while (R < q[i].r) add(a[++R]);
    while (L < q[i].l) del(a[L++]);
    while (R > q[i].r) del(a[R--]);
    while (tim < q[i].t) apply(++tim, L, R);
    while (tim > q[i].t) apply(tim--, L, R);
    ans[q[i].id] = n + 1;
    for (int l = rit[0] + 1, r; l <= n; l = rit[ord[l]] + 1) {
      for (r = l; r <= n && (r = rit[ord[r]]) - l + 1 < q[i].k; ++r);
      if (r > n) break; 
      else ans[q[i].id] = min(ans[q[i].id], ord[r] - ord[l]); 
    }
    if (ans[q[i].id] == n + 1) ans[q[i].id] = -1;
  }
  for (int i = 1; i <= cntq; i++) printf("%d\n", ans[i]);
  return 0;
}