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;
int n, m, T, q, r, sum, a[200100], b[200100], c[200100];
int ans[200100];
map<int, int> ma;
struct node {
  int x, y, id, tim;
  bool operator<(node u) const {
    return x / T == u.x / T ? (y / T == u.y / T ? tim < u.tim : y < u.y)
                            : x < u.x;
  }
} que[200100];
struct change {
  int p, c;
} chg[200100];
struct node1 {
  int s, id;
  bool operator<(node1 u) const { return s < u.s; }
} qwe[400100];
inline void add(register int x) {
  b[c[a[x]]]--;
  c[a[x]]++;
  b[c[a[x]]]++;
}
inline void del(register int x) {
  b[c[a[x]]]--;
  c[a[x]]--;
  b[c[a[x]]]++;
}
inline void change(register int x, register int t) {
  if (que[x].x <= chg[t].p && chg[t].p <= que[x].y) {
    del(chg[t].p);
    int tmp = a[chg[t].p];
    a[chg[t].p] = chg[t].c;
    add(chg[t].p);
    a[chg[t].p] = tmp;
  }
  swap(a[chg[t].p], chg[t].c);
}
inline void write(register int x) {
  if (!x) {
    return;
  }
  write(x / 10);
  putchar(x % 10 + '0');
  return;
}
inline void read(int &x) {
  char c = getchar();
  x = 0;
  while (c < '0' || c > '9') {
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 3) + (x << 1) + (c ^ 48);
    c = getchar();
  }
}
int main() {
  read(n);
  read(m);
  T = pow(n, 0.66666);
  for (int i = 1; i <= n; i++) {
    read(qwe[i].s);
    qwe[i].id = i;
  }
  int sum1 = 0;
  for (int i = 1; i <= m; i++) {
    int qwq;
    read(qwq);
    if (qwq == 1) {
      q++;
      read(que[q].x);
      read(que[q].y);
      que[q].tim = r;
      que[q].id = q;
    } else {
      r++;
      read(chg[r].p);
      read(qwe[r + n].s);
      qwe[r + n].id = r + n;
    }
  }
  stable_sort(qwe + 1, qwe + 1 + r + n);
  for (int i = 1; i <= r + n; i++) {
    if (qwe[i].s > qwe[i - 1].s) {
      sum1++;
    }
    if (qwe[i].id <= n) {
      a[qwe[i].id] = sum1;
    } else {
      chg[qwe[i].id - n].c = sum1;
    }
  }
  b[0] = sum;
  stable_sort(que + 1, que + 1 + q);
  int x = 1, y = 0, cnt = 0;
  for (int i = 1; i <= q; i++) {
    int qx = que[i].x, qy = que[i].y;
    while (x < qx) {
      del(x);
      x++;
    }
    while (x > qx) {
      x--;
      add(x);
    }
    while (y < qy) {
      y++;
      add(y);
    }
    while (y > qy) {
      del(y);
      y--;
    }
    while (cnt < que[i].tim) {
      cnt++;
      change(i, cnt);
    }
    while (cnt > que[i].tim) {
      change(i, cnt);
      cnt--;
    }
    sum = 0;
    while (b[sum + 1] != 0) {
      sum++;
    }
    ans[que[i].id] = sum + 1;
  }
  for (int i = 1; i <= q; i++) {
    write(ans[i]);
    putchar('\n');
  }
  return 0;
}