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;
long long a[200006], b[200006], L = 1, R = 1, ID, ans[200006], TIM,
                                lishan[200006], n, m, sum[200006], tot[200006];
long long licnt, type;
inline long long read() {
  long long w = 1, tmp = 0;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    tmp = (tmp << 1) + (tmp << 3) + ch - '0';
    ch = getchar();
  }
  return w * tmp;
}
inline void shuchu(long long x) {
  if (x < 0) x = ~x + 1, putchar('-');
  if (x > 9) shuchu(x / 10);
  putchar(x % 10 + 48);
}
struct edge {
  long long l, r, arear, areal, tim, id;
  bool operator<(const edge &a) const {
    if (areal == a.areal) {
      if (arear == a.arear) return tim < a.tim;
      return r < a.r;
    }
    return l < a.l;
  }
} es[200006];
struct cha {
  long long pos, newc, oldc;
} re[200006];
inline void change(long long x, long long k) {
  sum[x] += k;
  tot[sum[x]]++;
  tot[sum[x] - k]--;
}
inline void update(long long k) {
  if (k == 1) {
    a[re[TIM].pos] = re[TIM].newc;
  }
  if (k == -1) {
    a[re[TIM].pos] = re[TIM].oldc;
  }
  if (re[TIM].pos >= L && re[TIM].pos <= R) {
    if (k == 1) change(re[TIM].newc, 1), change(re[TIM].oldc, -1);
    if (k == -1) change(re[TIM].oldc, 1), change(re[TIM].newc, -1);
  }
}
signed main() {
  n = read();
  m = read();
  long long k = pow(n, 2.0 / 3.0);
  for (register long long i = 1; i <= n; i++) {
    a[i] = read();
    lishan[++licnt] = a[i];
  }
  for (register long long i = 1; i <= m; i++) {
    type = read();
    if (type == 1) {
      es[++ID].l = read();
      es[ID].r = read();
      es[ID].id = ID;
      es[ID].tim = TIM;
      es[ID].areal = es[ID].l / k;
      es[ID].arear = es[ID].r / k;
    } else {
      re[++TIM].pos = read();
      re[TIM].newc = read();
      lishan[++licnt] = re[TIM].newc;
    }
  }
  sort(lishan + 1, lishan + 1 + licnt);
  licnt = unique(lishan + 1, lishan + 1 + licnt) - lishan - 1;
  for (register long long i = 1; i <= n; i++) {
    b[i] = a[i] = lower_bound(lishan + 1, lishan + 1 + licnt, a[i]) - lishan;
  }
  for (long long i = 1; i <= TIM; i++) {
    re[i].newc =
        lower_bound(lishan + 1, lishan + 1 + licnt, re[i].newc) - lishan;
    re[i].oldc = b[re[i].pos];
    b[re[i].pos] = re[i].newc;
  }
  sort(es + 1, es + 1 + ID);
  sum[a[L]]++;
  tot[sum[a[L]]]++;
  TIM = 0;
  for (long long i = 1; i <= ID; i++) {
    while (TIM < es[i].tim) TIM++, update(1);
    while (TIM > es[i].tim) update(-1), TIM--;
    while (L > es[i].l) {
      L--;
      change(a[L], 1);
    }
    while (L < es[i].l) {
      change(a[L], -1);
      L++;
    }
    while (R < es[i].r) {
      R++;
      change(a[R], 1);
    }
    while (R > es[i].r) {
      change(a[R], -1);
      R--;
    }
    for (ans[es[i].id] = 1; tot[ans[es[i].id]] > 0; ans[es[i].id]++)
      ;
  }
  for (long long i = 1; i <= ID; i++) {
    shuchu(ans[i]);
    putchar('\n');
  }
}