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 std ::sort;
using std ::swap;
using std ::unique;
const int SIZE = 1 << 22 | 1;
namespace input {
char ibuf[SIZE], *iS, *iT;
inline char gc() {
  return iS == iT && (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), iS == iT)
             ? EOF
             : *iS++;
}
inline int geti() {
  register int x = 0;
  register char c = gc();
  while (!isdigit(c)) c = gc();
  for (; isdigit(c); c = gc()) x = x * 10 + (c & 15);
  return x;
}
}  // namespace input
using input::geti;
namespace output {
char obuf[SIZE], *oS = obuf, *oT = obuf + SIZE - 1, qu[15];
int qr;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char c) {
  *oS++ = c;
  if (oS == oT) flush();
}
inline void puti(int x) {
  while (x) {
    qu[++qr] = x % 10 + '0';
    x /= 10;
  }
  while (qr) putc(qu[qr--]);
}
struct Flusher {
  ~Flusher() { flush(); }
} flusher;
}  // namespace output
using output::putc;
using output::puti;
const int N = 100005;
int n, m, a[N], b[N << 1], qc, mc, tot, p[N], x[N], ans[N], bl[N], cnt[N << 1],
    cntc[N];
struct quest {
  int l, r, t, num;
} q[N];
bool cmpi(const int &lhs, const int &rhs) { return lhs < rhs; }
bool cmpq(const quest &lhs, const quest &rhs) {
  if (bl[lhs.l] != bl[rhs.l]) return lhs.l < rhs.l;
  if (bl[lhs.r] != bl[rhs.r]) return lhs.r < rhs.r;
  return lhs.t < rhs.t;
}
int search(int x) {
  int l = 1, r = tot;
  while (l <= r) {
    int mid = l + r >> 1;
    if (b[mid] == x) return mid;
    if (b[mid] < x)
      l = mid + 1;
    else
      r = mid - 1;
  }
}
inline void add(int x) {
  --cntc[cnt[x]];
  ++cnt[x];
  ++cntc[cnt[x]];
}
inline void del(int x) {
  --cntc[cnt[x]];
  --cnt[x];
  ++cntc[cnt[x]];
}
inline int getans() {
  for (int i = 1; i <= n; ++i) {
    if (!cntc[i]) return i;
  }
}
void work() {
  sort(b + 1, b + tot + 1, cmpi);
  tot = unique(b + 1, b + tot + 1) - b - 1;
  for (int i = 1; i <= n; ++i) {
    a[i] = search(a[i]);
  }
  for (int i = 1; i <= mc; ++i) {
    x[i] = search(x[i]);
  }
  int len = pow(n, 2.0 / 3.0);
  for (int i = 1; i <= n; ++i) {
    bl[i] = (i - 1) / len + 1;
  }
  sort(q + 1, q + qc + 1, cmpq);
  int l = q[1].l, r = q[1].r, now = 0;
  while (now < q[1].t) {
    ++now;
    swap(a[p[now]], x[now]);
  }
  for (int i = l; i <= r; ++i) {
    add(a[i]);
  }
  for (int i = 1; i <= qc; ++i) {
    while (l < q[i].l) {
      del(a[l++]);
    }
    while (l > q[i].l) {
      add(a[--l]);
    }
    while (r > q[i].r) {
      del(a[r--]);
    }
    while (r < q[i].r) {
      add(a[++r]);
    }
    while (now < q[i].t) {
      ++now;
      if (l <= p[now] && p[now] <= r) {
        del(a[p[now]]);
        add(x[now]);
      }
      swap(a[p[now]], x[now]);
    }
    while (now > q[i].t) {
      if (l <= p[now] && p[now] <= r) {
        del(a[p[now]]);
        add(x[now]);
      }
      swap(a[p[now]], x[now]);
      now--;
    }
    ans[q[i].num] = getans();
  }
}
int main() {
  n = geti();
  m = geti();
  for (int i = 1; i <= n; ++i) {
    a[i] = geti();
  }
  memcpy(b, a, sizeof(int) * (n + 1));
  tot = n;
  for (int i = 1; i <= m; ++i) {
    int op = geti();
    if (op == 2) {
      ++mc;
      p[mc] = geti();
      x[mc] = geti();
      b[++tot] = x[mc];
    } else {
      ++qc;
      q[qc].t = mc;
      q[qc].l = geti();
      q[qc].r = geti();
      q[qc].num = qc;
    }
  }
  work();
  for (int i = 1; i <= qc; ++i) {
    puti(ans[i]);
    putc('\n');
  }
  return 0;
}