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 long long M = 998244353;
const int N = 100005;
int n, q, a[N], lim, t[N * 2], p, ti, pre[N], aft[N], tmp[N], pos[N], m, tot,
    que, f[N * 2], vis[N * 2], l, r, tim, ans[N], op;
struct str {
  int x, y, z, ind;
} e[N];
bool cmp(str a, str b) {
  if (a.x / lim != b.x / lim) return a.x / lim < b.x / lim;
  if (a.y / lim != b.y / lim) return a.y / lim < b.y / lim;
  return a.z < b.z;
}
void dec(int x) {
  vis[f[x]]--;
  f[x]--;
  vis[f[x]]++;
}
void add(int x) {
  vis[f[x]]--;
  f[x]++;
  vis[f[x]]++;
}
int main() {
  scanf("%d %d", &n, &q);
  for (lim = 1; sqrt(1.0 * lim * lim * lim) <= n; ++lim)
    ;
  for (register int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    t[++m] = a[i];
    tmp[i] = a[i];
  }
  for (register int i = 1; i <= q; ++i) {
    scanf("%d", &op);
    if (op == 1) {
      ++que;
      scanf("%d %d", &e[que].x, &e[que].y);
      e[que].z = ti;
      e[que].ind = que;
    } else {
      ++ti;
      scanf("%d %d", &pos[ti], &aft[ti]);
      t[++m] = aft[ti];
      pre[ti] = tmp[pos[ti]];
      tmp[pos[ti]] = aft[ti];
    }
  }
  sort(t + 1, t + 1 + m);
  for (register int i = 1; i <= m; ++i)
    if (t[i] != t[tot]) t[++tot] = t[i];
  sort(e + 1, e + 1 + que, cmp);
  for (register int i = 1; i <= n; ++i)
    a[i] = lower_bound(t + 1, t + 1 + tot, a[i]) - t;
  for (register int i = 1; i <= ti; ++i) {
    aft[i] = lower_bound(t + 1, t + 1 + tot, aft[i]) - t;
    pre[i] = lower_bound(t + 1, t + 1 + tot, pre[i]) - t;
  }
  l = 1, r = 0, tim = 0;
  for (register int i = 1; i <= que; ++i) {
    while (r < e[i].y) {
      ++r;
      add(a[r]);
    }
    while (r > e[i].y) {
      dec(a[r]);
      --r;
    }
    while (l < e[i].x) {
      dec(a[l]);
      ++l;
    }
    while (l > e[i].x) {
      --l;
      add(a[l]);
    }
    while (tim < e[i].z) {
      ++tim;
      a[pos[tim]] = aft[tim];
      if (pos[tim] >= l && pos[tim] <= r) {
        dec(pre[tim]);
        add(aft[tim]);
      }
    }
    while (tim > e[i].z) {
      a[pos[tim]] = pre[tim];
      if (pos[tim] >= l && pos[tim] <= r) {
        dec(aft[tim]);
        add(pre[tim]);
      }
      --tim;
    }
    register int j;
    for (j = 1; vis[j]; ++j)
      ;
    ans[e[i].ind] = j;
  }
  for (register int i = 1; i <= que; i++) printf("%d\n", ans[i]);
}