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 <typename T>
void read(T &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= f;
}
inline void write(int x) {
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
const int N = 100005, M = 100005, Q = 100005;
int v[N << 1], lv;
int n, m, q, a[N];
int id[M], fr[N], to[N];
int csiz;
struct Ask {
  int id, l, r, t;
  inline bool operator<(const Ask w) const {
    if (l / csiz ^ w.l / csiz) return l < w.l;
    if (r / csiz ^ w.r / csiz) return r < w.r;
    return t < w.t;
  }
} ask[Q];
int ans[Q];
int cnt1[N + Q], cnt2[N + Q];
inline void Add(int x) { --cnt2[cnt1[x]], ++cnt1[x], ++cnt2[cnt1[x]]; }
inline void Dev(int x) { --cnt2[cnt1[x]], --cnt1[x], ++cnt2[cnt1[x]]; }
inline int Ask() {
  for (int i = 1;; ++i)
    if (!cnt2[i]) return i;
}
int main() {
  int i, qwq, op;
  read(n), lv = n, read(qwq);
  for (i = 1; i <= n; ++i) read(a[i]), v[i] = a[i];
  while (qwq--) {
    read(op);
    if (op == 1)
      ++q, read(ask[q].l), read(ask[q].r), ask[q].t = m, ask[q].id = q;
    else
      ++m, read(id[m]), fr[m] = a[id[m]], read(to[m]), a[id[m]] = to[m],
                        v[++lv] = to[m];
  }
  sort(v + 1, v + lv + 1), lv = unique(v + 1, v + lv + 1) - v - 1;
  for (i = 1; i <= n; ++i) a[i] = lower_bound(v + 1, v + lv + 1, a[i]) - v;
  for (i = 1; i <= m; ++i)
    fr[i] = lower_bound(v + 1, v + lv + 1, fr[i]) - v,
    to[i] = lower_bound(v + 1, v + lv + 1, to[i]) - v;
  csiz = 1 + pow(n, 0.6667);
  sort(ask + 1, ask + q + 1);
  int nl = 1, nr = 1, nt = m;
  Add(a[1]);
  for (i = 1; i <= q; ++i) {
    while (nt > ask[i].t) {
      if (nl <= id[nt] && id[nt] <= nr)
        Dev(a[id[nt]]), a[id[nt]] = fr[nt], Add(a[id[nt]]);
      else
        a[id[nt]] = fr[nt];
      --nt;
    }
    while (nt < ask[i].t) {
      ++nt;
      if (nl <= id[nt] && id[nt] <= nr)
        Dev(a[id[nt]]), a[id[nt]] = to[nt], Add(a[id[nt]]);
      else
        a[id[nt]] = to[nt];
    }
    while (nl > ask[i].l) --nl, Add(a[nl]);
    while (nr < ask[i].r) ++nr, Add(a[nr]);
    while (nl < ask[i].l) Dev(a[nl]), ++nl;
    while (nr > ask[i].r) Dev(a[nr]), --nr;
    ans[ask[i].id] = Ask();
  }
  for (i = 1; i <= q; ++i) write(ans[i]), putchar('\n');
  return 0;
}