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;
const int MAXN = 1e5 + 5, len = 2155, maxAns = 700, INF = 1e9;
struct Request {
  int t, ct, l, cl, r, ind;
  Request() : t(), ct(), l(), cl(), r(), ind() {}
  Request(int t, int l, int r, int ind)
      : t(t), ct(t / len), l(l), cl(l / len), r(r), ind(ind) {}
  bool operator<(const Request &req) const {
    if (ct != req.ct) {
      return ct < req.ct;
    } else if (cl != req.cl) {
      return (cl < req.cl);
    } else {
      return (r < req.r);
    }
  }
};
int n, m, q, timer, a[MAXN], x[MAXN], oldval[MAXN], newval[MAXN];
int v[2 * MAXN], sz, cnt[2 * MAXN], cntcnt[MAXN], ans[MAXN];
Request req[MAXN];
int main() {
  q = 0;
  timer = 0;
  sz = 0;
  memset(cnt, 0, sizeof(int) * 2 * MAXN);
  memset(cntcnt, 0, sizeof(int) * MAXN);
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
    v[sz++] = a[i];
  }
  int t, l, r, ind;
  for (int i = 0; i < m; ++i) {
    scanf("%d", &t);
    if (t == 1) {
      scanf("%d %d", &l, &r);
      --l;
      req[q] = Request(timer, l, r, q);
      ++q;
    } else {
      scanf("%d %d", &x[timer], &newval[timer]);
      --x[timer];
      oldval[timer] = a[x[timer]];
      a[x[timer]] = newval[timer];
      v[sz++] = newval[timer];
      ++timer;
    }
  }
  sort(v, v + sz);
  sz = unique(v, v + sz) - v;
  for (int i = 0; i < n; ++i) {
    a[i] = lower_bound(v, v + sz, a[i]) - v;
  }
  for (int i = 0; i < timer; ++i) {
    oldval[i] = lower_bound(v, v + sz, oldval[i]) - v;
    newval[i] = lower_bound(v, v + sz, newval[i]) - v;
  }
  sort(req, req + q);
  t = timer;
  l = 0;
  r = 0;
  for (int i = 0; i < q; ++i) {
    while (t < req[i].t) {
      if (l <= x[t] && x[t] < r) {
        --cntcnt[cnt[oldval[t]]];
        --cnt[oldval[t]];
        ++cntcnt[cnt[oldval[t]]];
        --cntcnt[cnt[newval[t]]];
        ++cnt[newval[t]];
        ++cntcnt[cnt[newval[t]]];
      }
      a[x[t]] = newval[t];
      ++t;
    }
    while (t > req[i].t) {
      --t;
      if (l <= x[t] && x[t] < r) {
        --cntcnt[cnt[newval[t]]];
        --cnt[newval[t]];
        ++cntcnt[cnt[newval[t]]];
        --cntcnt[cnt[oldval[t]]];
        ++cnt[oldval[t]];
        ++cntcnt[cnt[oldval[t]]];
      }
      a[x[t]] = oldval[t];
    }
    while (l > req[i].l) {
      --l;
      --cntcnt[cnt[a[l]]];
      ++cnt[a[l]];
      ++cntcnt[cnt[a[l]]];
    }
    while (r < req[i].r) {
      --cntcnt[cnt[a[r]]];
      ++cnt[a[r]];
      ++cntcnt[cnt[a[r]]];
      ++r;
    }
    while (l < req[i].l) {
      --cntcnt[cnt[a[l]]];
      --cnt[a[l]];
      ++cntcnt[cnt[a[l]]];
      ++l;
    }
    while (r > req[i].r) {
      --r;
      --cntcnt[cnt[a[r]]];
      --cnt[a[r]];
      ++cntcnt[cnt[a[r]]];
    }
    ind = req[i].ind;
    ans[ind] = 1;
    while (cntcnt[ans[ind]]) {
      ++ans[ind];
    }
  }
  for (int i = 0; i < q; ++i) {
    printf("%d\n", ans[i]);
  }
  return 0;
}