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;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, m, q;
int a[200000];
int used[200000], cnt[200000];
struct node {
  int l, r, num, lk, rk, t;
} b[200000];
struct node2 {
  int num, col;
} c[200000];
struct node3 {
  bool f;
  int v, num;
} d[500000];
inline bool cmp2(node3 x, node3 y) { return x.v < y.v; }
inline bool cmp(node x, node y) {
  if (x.lk == y.lk) {
    if (x.rk == y.rk) return x.t < y.t;
    return x.rk < y.rk;
  }
  return x.lk < y.lk;
}
int la[200000];
int l, r, ans, o = 1, pro, cha, tim, tot;
int main() {
  n = read(), m = 2500, q = read();
  for (register int i = 1; i <= n; ++i)
    d[i].v = read(), d[i].f = 1, d[i].num = i;
  for (register int i = 1; i <= q; ++i) {
    int z;
    int x, y;
    z = read();
    x = read(), y = read();
    if (z == 1) {
      ++pro;
      b[pro].l = x;
      b[pro].r = y;
      b[pro].lk = (b[pro].l - 1) / m + 1;
      b[pro].rk = (b[pro].r - 1) / m + 1;
      b[pro].num = pro;
      b[pro].t = cha;
    } else {
      ++cha;
      c[cha].num = x;
      c[cha].col = y;
      d[n + cha].v = y;
      d[n + cha].f = 0;
      d[n + cha].num = cha;
    }
  }
  sort(d + 1, d + n + cha + 1, cmp2);
  for (int i = 1; i <= n + cha; ++i) {
    if (d[i - 1].v != d[i].v) ++tot;
    if (d[i].f)
      a[d[i].num] = tot;
    else
      c[d[i].num].col = tot;
  }
  sort(b + 1, b + pro + 1, cmp);
  l = b[1].l, r = b[1].l - 1;
  int p = pro;
  while (p--) {
    while (r < b[o].r)
      --cnt[used[a[r + 1]]], ++cnt[used[a[r + 1]] + 1], ans += !used[a[++r]]++;
    while (r > b[o].r)
      --cnt[used[a[r]]], ++cnt[used[a[r]] - 1], ans -= !--used[a[r--]];
    while (l < b[o].l)
      --cnt[used[a[l]]], ++cnt[used[a[l]] - 1], ans -= !--used[a[l++]];
    while (l > b[o].l)
      --cnt[used[a[l - 1]]], ++cnt[used[a[l - 1]] + 1], ans += !used[a[--l]]++;
    while (tim < b[o].t) {
      if (c[++tim].num >= b[o].l && c[tim].num <= b[o].r) {
        int nnn = c[tim].num;
        --cnt[used[a[nnn]]];
        ++cnt[used[a[nnn]] - 1];
        ans -= !--used[a[nnn]];
        swap(a[nnn], c[tim].col);
        --cnt[used[a[nnn]]];
        ++cnt[used[a[nnn]] + 1];
        ans += !used[a[nnn]]++;
      } else
        swap(a[c[tim].num], c[tim].col);
    }
    while (tim > b[o].t) {
      if (c[tim].num >= b[o].l && c[tim].num <= b[o].r) {
        int nnn = c[tim].num;
        --cnt[used[a[nnn]]];
        ++cnt[used[a[nnn]] - 1];
        ans -= !--used[a[nnn]];
        swap(a[nnn], c[tim].col);
        --cnt[used[a[nnn]]];
        ++cnt[used[a[c[tim--].num]] + 1];
        ans += !used[a[nnn]]++;
      } else
        swap(a[c[tim].num], c[tim].col), tim--;
    }
    int c = 0;
    while (cnt[++c])
      ;
    la[b[o].num] = c, ++o;
  }
  for (register int i = 1; i <= pro; i++) printf("%d\n", la[i]);
  return 0;
}