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::lower_bound;
using std::sort;
using std::swap;
using std::unique;
const int N(3e5 + 5);
template <class type>
inline const void read(type &in) {
  in = 0;
  char ch(getchar());
  while (ch < 48 || ch > 57) ch = getchar();
  while (ch > 47 && ch < 58)
    in = (in << 3) + (in << 1) + (ch & 15), ch = getchar();
}
int belong[N], n, m, target[N], goal[N], cnt[N], num[N], lsh[N], a[N], ans[N],
    tot;
struct query {
  int l, r, t, id;
  inline query() {}
  inline query(const int &l, const int &r, const int &t, const int &id)
      : l(l), r(r), t(t), id(id) {}
  inline const bool operator<(const query &q) const {
    return belong[l] ^ belong[q.l]   ? belong[l] < belong[q.l]
           : belong[r] ^ belong[q.r] ? belong[r] < belong[q.r]
                                     : t < q.t;
  }
} q[N];
inline const int pos(const int &x) {
  return lower_bound(lsh + 1, lsh + tot + 1, x) - lsh;
}
inline const void add(const int &x) {
  if (cnt[a[x]]) num[cnt[a[x]]]--;
  num[++cnt[a[x]]]++;
}
inline const void del(const int &x) {
  num[cnt[a[x]]]--;
  if (cnt[a[x]]) num[--cnt[a[x]]]++;
}
inline const void upd(const int &x, const int &l, const int &r) {
  const int p(target[x]);
  if (p >= l && p <= r) del(p);
  swap(a[p], goal[x]);
  if (p >= l && p <= r) add(p);
}
inline const int ask() {
  for (int i(1); i <= n; i++)
    if (!num[i]) return i;
}
int main() {
  read(n);
  read(m);
  for (int i(1); i <= n; i++) read(a[i]), lsh[++tot] = a[i];
  int l(1), r(0), t(0), qcnt(0), ccnt(0);
  for (int i(1), opt, x, y; i <= m; i++)
    if (read(opt), read(x), read(y), opt & 1)
      qcnt++, q[qcnt] = query(x, y, ccnt, qcnt);
    else
      target[++ccnt] = x, lsh[++tot] = goal[ccnt] = y;
  sort(lsh + 1, lsh + tot + 1);
  tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
  for (int i(1); i <= n; i++) a[i] = pos(a[i]);
  for (int i(1); i <= ccnt; i++) goal[i] = pos(goal[i]);
  const int size(pow(n, 2.0 / 3));
  for (int i(1); i <= n; i++) belong[i] = (i - 1) / size + 1;
  sort(q + 1, q + qcnt + 1);
  for (int i(1); i <= m; i++) {
    while (r < q[i].r) add(++r);
    while (l > q[i].l) add(--l);
    while (r > q[i].r) del(r--);
    while (l < q[i].l) del(l++);
    while (t < q[i].t) upd(++t, l, r);
    while (t > q[i].t) upd(t--, l, r);
    ans[q[i].id] = ask();
  }
  for (int i(1); i <= qcnt; i++) printf("%d\n", ans[i]);
  return 0;
}