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 N = 2e5 + 5;
int n, m, T, len, size, l, r, tim, ql, qr, qt, qtot, ctot;
int res[N], cnt[N], sum[N], v[N], Hash[N], Cnt[N];
struct Q {
  int l, r, id, lblock, rblock, tim;
} q[N];
struct C {
  int pos, color;
} c[N];
inline void read(int &tmp) {
  register char c = getchar();
  for (tmp = 0; !isdigit(c); c = getchar())
    ;
  for (; isdigit(c); tmp = tmp * 10 + c - 48, c = getchar())
    ;
}
inline bool cmp(const Q &a, const Q &b) {
  return (a.lblock ^ b.lblock)   ? a.lblock < b.lblock
         : (a.rblock ^ b.rblock) ? a.rblock < b.rblock
                                 : a.tim < b.tim;
}
inline void add(int p) {
  int &x = cnt[p];
  if (!--Cnt[x]) --sum[(((x)-1) / size + 1)];
  if (!Cnt[++x]++) ++sum[(((x)-1) / size + 1)];
}
inline void del(int p) {
  int &x = cnt[p];
  if (!--Cnt[x]) --sum[(((x)-1) / size + 1)];
  if (!Cnt[--x]++) ++sum[(((x)-1) / size + 1)];
}
inline void modify(int p) {
  if (ql <= c[p].pos && c[p].pos <= qr) del(v[c[p].pos]), add(c[p].color);
  swap(c[p].color, v[c[p].pos]);
}
inline int ask() {
  for (int i = 1; i <= (((n)-1) / size + 1); ++i)
    if (sum[i] != size)
      for (int j = (((i)-1) * size + 1); j <= (min((i)*size, n)); ++j)
        if (!Cnt[j]) return j;
}
int main() {
  read(n);
  read(m);
  len = ceil(pow(n * 1.0, 2.0 / 3.0));
  size = ceil(pow(n * 1.0, 0.5));
  for (int i = 1; i <= n; ++i) read(v[i]), Hash[++T] = v[i];
  for (int i = 1, op, a, b; i <= m; ++i) {
    read(op);
    read(a);
    read(b);
    if (op == 1) {
      q[++qtot].tim = ctot;
      q[qtot].l = a;
      q[qtot].r = b;
      q[qtot].id = qtot;
      q[qtot].lblock = (q[qtot].l - 1) / len + 1;
      q[qtot].rblock = (q[qtot].r - 1) / len + 1;
    } else {
      c[++ctot].pos = a;
      c[ctot].color = Hash[++T] = b;
    }
  }
  sort(Hash + 1, Hash + 1 + T);
  T = unique(Hash + 1, Hash + 1 + T) - Hash - 1;
  for (int i = 1; i <= n; ++i)
    v[i] = lower_bound(Hash + 1, Hash + 1 + T, v[i]) - Hash;
  for (int i = 1; i <= ctot; ++i)
    c[i].color = lower_bound(Hash + 1, Hash + 1 + T, c[i].color) - Hash;
  sort(q + 1, q + 1 + qtot, cmp);
  l = q[1].l, r = l - 1;
  for (int i = 1; i <= qtot; ++i) {
    ql = q[i].l;
    qr = q[i].r;
    qt = q[i].tim;
    while (l < ql) del(v[l++]);
    while (l > ql) add(v[--l]);
    while (r < qr) add(v[++r]);
    while (r > qr) del(v[r--]);
    while (tim < qt) modify(++tim);
    while (tim > qt) modify(tim--);
    res[q[i].id] = ask();
  }
  for (int i = 1; i <= qtot; ++i) printf("%d\n", res[i]);
  return 0;
}