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;
template <class T>
ostream& operator<<(ostream& in, vector<T>& arr) {
  for (T& i : arr) {
    in << i << " ";
  }
  return in;
}
struct req {
  int l, r, t, ind;
  req() : l(0), r(0), t(0){};
  req(int l, int r, int t, int ind) : l(l), r(r), t(t), ind(ind){};
};
int k;
bool cmp(const req& x, const req& y) {
  if (x.l / k == y.l / k) {
    const int a = (x.l / k) & 1;
    if (x.r / k == y.r / k) {
      const int b = (x.r / k) & 1;
      return (a != b ? x.t < y.t : x.t > y.t);
    }
    return (a ? x.r < y.r : x.r > y.r);
  }
  return x.l < y.l;
}
pair<int, int> x[(int)(1e5 + 1)];
vector<int> a;
vector<int> cnt;
vector<int> b;
inline void addcnt(int val) {
  int bl = val / k;
  if (cnt[val] == 0) b[bl]--;
  cnt[val]++;
}
inline void delcnt(int val) {
  int bl = val / k;
  cnt[val]--;
  if (cnt[val] == 0) b[bl]++;
}
vector<int> valcnt;
inline void add(int val) {
  if (valcnt[val] != 0) {
    delcnt(valcnt[val]);
  }
  valcnt[val]++;
  addcnt(valcnt[val]);
}
inline void del(int val) {
  delcnt(valcnt[val]);
  valcnt[val]--;
  if (valcnt[val] > 0) addcnt(valcnt[val]);
}
inline void addchange(int ind, int l, int r) {
  if (x[ind].first >= l && x[ind].first <= r) {
    del(a[x[ind].first]);
    add(x[ind].second);
  }
  a[x[ind].first] = x[ind].second;
}
int pr[(int)(1e5 + 1)];
inline void delchange(int ind, int l, int r) {
  if (x[ind].first >= l && x[ind].first <= r) {
    del(a[x[ind].first]);
    add(pr[ind]);
  }
  a[x[ind].first] = pr[ind];
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, q;
  cin >> n >> q;
  a.resize(n);
  unordered_map<int, int> used;
  used.max_load_factor(0.25);
  used.reserve(n + q);
  int valscount = 0;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    if (used.count(a[i]))
      a[i] = used[a[i]];
    else {
      used[a[i]] = valscount;
      a[i] = valscount;
      valscount++;
    }
  }
  k = 2150;
  vector<int> a_ = a;
  int c = 0;
  vector<req> r;
  for (int i = 0; i < q; ++i) {
    int t;
    cin >> t;
    if (t == 1) {
      int l, r_;
      cin >> l >> r_;
      --l;
      --r_;
      r.push_back(req(l, r_, c, i - c));
    } else {
      int p, val;
      cin >> p >> val;
      --p;
      if (used.count(val))
        val = used[val];
      else {
        used[val] = valscount;
        val = valscount;
        valscount++;
      }
      pr[c] = a[p];
      a[p] = val;
      x[c] = {p, val};
      c++;
    }
  }
  a = a_;
  sort(r.begin(), r.end(), cmp);
  int curx = 0, cury = -1, curt = 0;
  cnt.resize((int)(2e5) + 5, 0);
  b.resize((int)(2e5) + 5, k);
  valcnt.resize((int)2e5 + 5, 0);
  int res[q - c];
  for (auto el : r) {
    while (curx > el.l) {
      curx--;
      add(a[curx]);
    }
    while (cury < el.r) {
      cury++;
      add(a[cury]);
    }
    while (curx < el.l) {
      del(a[curx]);
      curx++;
    }
    while (cury > el.r) {
      del(a[cury]);
      cury--;
    }
    while (curt < el.t) {
      curt++;
      addchange(curt - 1, el.l, el.r);
    }
    while (curt > el.t) {
      delchange(curt - 1, el.l, el.r);
      curt--;
    }
    int bl = 0;
    for (int i = 0; i < b.size(); ++i) {
      if ((i != 0 && b[i] > 0) || (i == 0 && b[i] > 1)) {
        bl = i;
        break;
      }
    }
    for (int i = bl * k; i < (bl + 1) * k; ++i) {
      if (cnt[i] == 0 && i != 0) {
        res[el.ind] = i;
        break;
      }
    }
  }
  for (auto p : res) {
    cout << p << '\n';
  }
  return 0;
}