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 int maxn = 2e5 + 50;
int n, m, tpq, tpc, len, a[maxn], tot;
int cnt[maxn], cnt2[maxn], ans[maxn];
struct que {
  int id, l, r, tim;
  bool operator<(que i) const {
    return l / len == i.l / len ? (r / len == i.r / len ? tim < i.tim : r < i.r)
                                : l < i.l;
  }
} q[maxn];
struct cha {
  int pos, col;
} c[maxn];
inline void add(int x) {
  cnt2[cnt[a[x]]]--;
  cnt[a[x]]++;
  cnt2[cnt[a[x]]]++;
}
inline void del(int x) {
  cnt2[cnt[a[x]]]--;
  cnt[a[x]]--;
  cnt2[cnt[a[x]]]++;
}
inline void modify(int id, int x) {
  if (c[x].pos >= q[id].l && c[x].pos <= q[id].r) {
    int tmp = a[c[x].pos];
    del(c[x].pos);
    a[c[x].pos] = c[x].col;
    add(c[x].pos);
    a[c[x].pos] = tmp;
  }
  swap(a[c[x].pos], c[x].col);
}
struct node {
  int id, x, y;
} b[maxn * 2];
int tp;
bool cmp1(node a, node b) { return a.id < b.id; }
bool cmp2(node a, node b) { return a.x < b.x; }
inline int read() {
  register int x = 0, y = 1;
  register char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') y = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
  return x * y;
}
int main() {
  n = read();
  m = read();
  len = pow(n, 0.66666);
  for (register int i = 1; i <= n; i++) {
    a[i] = read();
    b[++tp].id = i;
    b[tp].x = b[tp].y = a[i];
  }
  for (register int i = 1; i <= m; i++) {
    register int ch;
    ch = read();
    if (ch == 1) {
      tpq++;
      q[tpq].id = tpq;
      q[tpq].tim = tpc;
      q[tpq].l = read();
      q[tpq].r = read();
    } else {
      tpc++;
      c[tpc].pos = read();
      c[tpc].col = read();
      b[++tp].id = i + n;
      b[tp].x = b[tp].y = c[tpc].col;
    }
  }
  stable_sort(b + 1, b + 1 + tp, cmp2);
  b[1].x = 1;
  for (register int i = 2; i <= tp; i++) {
    if (b[i - 1].y == b[i].y)
      b[i].x = b[i - 1].x;
    else
      b[i].x = b[i - 1].x + 1;
  }
  stable_sort(b + 1, b + 1 + tp, cmp1);
  for (register int i = 1; i <= tp; i++) {
    if (i <= n)
      a[i] = b[i].x;
    else
      c[i - n].col = b[i].x;
  }
  stable_sort(q + 1, q + 1 + tpq);
  int l = 0, r = 0, cur = 0;
  for (register int i = 1; i <= tpq; i++) {
    while (l < q[i].l) {
      del(l);
      l++;
    }
    while (l > q[i].l) {
      add(l - 1);
      l--;
    }
    while (r < q[i].r) {
      add(r + 1);
      r++;
    }
    while (r > q[i].r) {
      del(r);
      r--;
    }
    while (cur < q[i].tim) {
      modify(i, cur + 1);
      cur++;
    }
    while (cur > q[i].tim) {
      modify(i, cur);
      cur--;
    }
    register int res = 0;
    while (cnt2[res + 1] != 0) res++;
    ans[q[i].id] = res + 1;
  }
  for (int i = 1; i <= tpq; i++) printf("%d\n", ans[i]);
  return 0;
}