Problem: You come home and fell some unpleasant smell. Where is it coming from?

You are given an array a. You have to answer the following queries: 

  1. You are given two integers l and r. Let ci be the number of occurrences of i in al: r, where al: r is the subarray of a from l-th element to r-th inclusive. Find the Mex of {c0, c1, ..., c109}
  2. You are given two integers p to x. Change ap to x. 



The Mex of a multiset of numbers is the smallest non-negative integer not in the set.

Note that in this problem all elements of a are positive, which means that c0 = 0 and 0 is never the answer for the query of the second type.

Input

The first line of input contains two integers n and q (1 ≤ n, q ≤ 100 000) — the length of the array and the number of queries respectively.

The second line of input contains n integers — a1, a2, ..., an (1 ≤ ai ≤ 109).

Each of the next q lines describes a single query.

The first type of query is described by three integers ti = 1, li, ri, where 1 ≤ li ≤ ri ≤ n — the bounds of the subarray.

The second type of query is described by three integers ti = 2, pi, xi, where 1 ≤ pi ≤ n is the index of the element, which must be changed and 1 ≤ xi ≤ 109 is the new value.

Output

For each query of the first type output a single integer — the Mex of {c0, c1, ..., c109}.

Example

Input

10 4
1 2 3 1 1 2 2 2 9 9
1 1 1
1 2 8
2 7 1
1 2 8


Output

2
3
2

Note

The subarray of the first query consists of the single element — 1. 

The subarray of the second query consists of four 2s, one 3 and two 1s.

The subarray of the fourth query consists of three 1s, three 2s and one 3.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int cyc(int x, int d) {
  if (!d) return x;
  if (d == 1) return x >> 1 | (x & 1) << 2;
  return x >> 2 | (x & 3) << 1;
}
long long hilbert3d(int x, int y, int z, int m) {
  static int E[] = {0, 0, 0, 3, 3, 6, 6, 5};
  static int D[] = {0, 1, 1, 2, 2, 1, 1, 0};
  static int rev[] = {0, 1, 3, 2, 7, 6, 4, 5};
  long long h = 0;
  int e = 0, d = 0;
  for (int i = m - 1; i >= 0; --i) {
    int l = (x >> i & 1) << 2 | (y >> i & 1) << 1 | (z >> i & 1);
    int w = rev[cyc(l ^ e, d)];
    h = h << 3 | w;
    e = e ^ cyc(E[w], (3 - d) % 3);
    d = (d + D[w] + 1) % 3;
  }
  return h;
}
int blo = 2000;
struct qry {
  int l, r, id, tim;
  long long ord;
  bool operator<(const qry &q) const {
    if (l / blo != q.l / blo)
      return l / blo < q.l / blo;
    else if (r / blo != q.r / blo)
      return r / blo < q.r / blo;
    return tim < q.tim;
  }
};
int pos[200005], val[200005], lstval[200005], cnt[200005], cnt2[200005];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  blo = n / pow(m * 1.0 / 2, 1.0 / 3);
  vector<int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  vector<int> aa = a;
  vector<qry> qs;
  int lg = 0;
  while (1 << lg < n) ++lg;
  while (1 << lg < m) ++lg;
  int tot = 0, qcnt = 0;
  for (int i = 0; i < m; ++i) {
    int op, l, r;
    cin >> op >> l >> r;
    if (op == 1) {
      --l, --r;
      qs.push_back({l, r, qcnt, tot, hilbert3d(l, r, tot, lg)});
      ++qcnt;
    } else {
      ++tot;
      pos[tot] = l - 1;
      val[tot] = r;
      aa.push_back(r);
    }
  }
  sort(aa.begin(), aa.end());
  aa.resize(unique(aa.begin(), aa.end()) - aa.begin());
  auto f = [&](int x) {
    return lower_bound(aa.begin(), aa.end(), x) - aa.begin();
  };
  for (int &i : a) i = f(i);
  for (int i = 1; i <= tot; ++i) val[i] = f(val[i]);
  sort(qs.begin(), qs.end());
  int l = 0, r = -1, tim = 0;
  vector<long long> ans(m);
  auto add = [&](int x) {
    cnt2[cnt[a[x]]]--;
    cnt[a[x]]++;
    cnt2[cnt[a[x]]]++;
  };
  auto del = [&](int x) {
    cnt2[cnt[a[x]]]--;
    cnt[a[x]]--;
    cnt2[cnt[a[x]]]++;
  };
  for (auto q : qs) {
    while (r < q.r) {
      ++r;
      add(r);
    }
    while (l > q.l) {
      --l;
      add(l);
    }
    while (r > q.r) {
      del(r);
      --r;
    }
    while (l < q.l) {
      del(l);
      ++l;
    }
    while (tim < q.tim) {
      ++tim;
      lstval[tim] = a[pos[tim]];
      if (pos[tim] >= l && pos[tim] <= r) {
        del(pos[tim]);
        a[pos[tim]] = val[tim];
        add(pos[tim]);
      } else {
        a[pos[tim]] = val[tim];
      }
    }
    while (tim > q.tim) {
      if (pos[tim] >= l && pos[tim] <= r) {
        del(pos[tim]);
        a[pos[tim]] = lstval[tim];
        add(pos[tim]);
      } else {
        a[pos[tim]] = lstval[tim];
      }
      --tim;
    }
    int res = 1;
    while (cnt2[res]) ++res;
    ans[q.id] = res;
  }
  for (int i = 0; i < qcnt; ++i) cout << ans[i] << "\n";
}