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;
struct Qu {
  int tp, lp, l, r, t, idx;
  bool operator<(Qu d) const {
    if (tp != d.tp) return tp < d.tp;
    if (lp != d.lp) return lp < d.lp;
    return r < d.r;
  };
} qu[100005];
struct Change {
  int idx, px, x;
} change[100005];
int arr[100005], ans[100005], chk[100005], cnt[2 * 100005];
int n, cn, qn;
int L, R, T;
int C;
map<int, int> num;
int uni(int x) { return num.count(x) ? num[x] : num[x] = C++; }
void add(int x) {
  chk[cnt[x]]--;
  chk[++cnt[x]]++;
}
void del(int x) {
  chk[cnt[x]]--;
  chk[--cnt[x]]++;
}
void change_arr(int idx, int x) {
  if (idx >= L && idx <= R) {
    add(x);
    del(arr[idx]);
  }
  arr[idx] = x;
}
int get(int l, int r, int t) {
  int i;
  while (T < t) {
    T++;
    change_arr(change[T].idx, change[T].x);
  }
  while (T > t) {
    change_arr(change[T].idx, change[T].px);
    T--;
  }
  for (i = L; i <= R; i++) {
    if (i >= l && i <= r) {
      i = r;
      continue;
    }
    del(arr[i]);
  }
  for (i = l; i <= r; i++) {
    if (i >= L && i <= R) {
      i = R;
      continue;
    }
    add(arr[i]);
  }
  L = l;
  R = r;
  for (i = 1; chk[i]; i++)
    ;
  return i;
}
int main() {
  int i, p, tp, l, r, q, x;
  scanf("%d %d", &n, &q);
  for (i = 1; i <= n; i++) {
    scanf("%d", &x);
    arr[i] = uni(x);
  }
  p = pow((double)n, 0.666);
  while (q--) {
    scanf("%d %d %d", &tp, &l, &r);
    if (tp == 1)
      qu[qn] = {cn / p, l / p, l, r, cn, qn}, qn++;
    else
      cn++, change[cn] = {l, -1, uni(r)};
  }
  for (i = 1; i <= cn; i++) {
    change[i].px = arr[change[i].idx];
    arr[change[i].idx] = change[i].x;
  }
  L = 0;
  R = -1;
  sort(qu, qu + qn);
  T = cn;
  for (i = 0; i < qn; i++) ans[qu[i].idx] = get(qu[i].l, qu[i].r, qu[i].t);
  for (i = 0; i < qn; i++) printf("%d\n", ans[i]);
  return 0;
}