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>
template <typename Tp>
inline void read(Tp& x) {
  x = 0;
  bool fg = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') fg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 1) + (x << 3) + (Tp)(ch ^ 48), ch = getchar();
  if (fg) x = -x;
}
template <typename Tp, typename... Args>
void read(Tp& t, Args&... args) {
  read(t);
  read(args...);
}
using namespace std;
const int N = 200010;
int a[N], ans[N], val[N << 1], totval;
struct quer {
  int id, l, r, t;
} q[N];
struct modi {
  int p, Old, New;
} m[N];
int n, Q, bl[N], B, totq, totm;
int ct[N], vs[N];
int l = 1, r = 0, t = 0;
int getmex() {
  for (int i = 1;; ++i)
    if (vs[i] == 0) return i;
}
void upd(int vl, int k) {
  --vs[ct[vl]];
  ct[vl] += k;
  ++vs[ct[vl]];
}
void updM(int id, int k) {
  if (k == 1) {
    m[id].Old = a[m[id].p];
    a[m[id].p] = m[id].New;
    if (l <= m[id].p && m[id].p <= r) {
      upd(m[id].Old, -1);
      upd(m[id].New, 1);
    }
  } else {
    a[m[id].p] = m[id].Old;
    if (l <= m[id].p && m[id].p <= r) {
      upd(m[id].New, -1);
      upd(m[id].Old, 1);
    }
  }
}
int main() {
  read(n, Q);
  for (int i = 1; i <= n; ++i) read(a[i]), val[++totval] = a[i];
  B = max(1, (int)pow(n, 2.0 / 3.0));
  for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / B + 1;
  for (int i = 1; i <= Q; ++i) {
    int op;
    read(op);
    if (op == 1) {
      ++totq;
      read(q[totq].l, q[totq].r);
      q[totq].id = totq;
      q[totq].t = totm;
    } else {
      ++totm;
      read(m[totm].p, m[totm].New);
      val[++totval] = m[totm].New;
    }
  }
  sort(val + 1, val + totval + 1);
  totval = unique(val + 1, val + totval + 1) - val - 1;
  for (int i = 1; i <= n; ++i)
    a[i] = lower_bound(val + 1, val + totval + 1, a[i]) - val;
  for (int i = 1; i <= totm; ++i)
    m[i].New = lower_bound(val + 1, val + totval + 1, m[i].New) - val;
  sort(q + 1, q + totq + 1, [](quer& a, quer& b) {
    int ida = bl[a.l] * 10000 + bl[a.r];
    int idb = bl[b.l] * 10000 + bl[b.r];
    return ida != idb ? ida < idb : a.t < b.t;
  });
  for (int i = 1; i <= totq; ++i) {
    while (l > q[i].l) upd(a[--l], 1);
    while (r < q[i].r) upd(a[++r], 1);
    while (l < q[i].l) upd(a[l++], -1);
    while (r > q[i].r) upd(a[r--], -1);
    while (t < q[i].t) updM(++t, 1);
    while (t > q[i].t) updM(t--, -1);
    ans[q[i].id] = getmex();
  }
  for (int i = 1; i <= totq; ++i) {
    printf("%d\n", ans[i]);
  }
  return 0;
}