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>
const int inf = 0x3f3f3f3f;
const int inn = 0x80808080;
using namespace std;
const int maxm = 2e+5;
struct Query {
  int l, r, x, id;
  Query(){};
  Query(int a, int b, int c, int d) { l = a, r = b, x = c, id = d; }
} q[maxm];
struct Change {
  int x, y;
  Change(){};
  Change(int xx, int yy) { x = xx, y = yy; }
} c[maxm];
int a[maxm];
int cnt[maxm], sum[maxm];
int xx[maxm << 1], num;
int numq, numc;
int n, m;
int block;
int res[maxm];
bool cmp(Query a, Query b) {
  if (a.l / block != b.l / block) {
    return a.l < b.l;
  } else if (a.r / block != b.r / block) {
    return a.r < b.r;
  } else {
    return a.x < b.x;
  }
}
void add(int x) {
  sum[cnt[a[x]]]--;
  cnt[a[x]]++;
  sum[cnt[a[x]]]++;
}
void del(int x) {
  sum[cnt[a[x]]]--;
  cnt[a[x]]--;
  sum[cnt[a[x]]]++;
}
void change(int x, int l, int r) {
  if (c[x].x >= l && c[x].x <= r) {
    del(c[x].x);
  }
  swap(a[c[x].x], c[x].y);
  if (c[x].x >= l && c[x].x <= r) {
    add(c[x].x);
  }
}
void solve() {
  int l = q[1].l, r = l - 1, now = 0;
  for (int i = 1; i <= numq; i++) {
    int ql = q[i].l, qr = q[i].r, x = q[i].x;
    while (l > ql) add(--l);
    while (l < ql) del(l++);
    while (r > qr) del(r--);
    while (r < qr) add(++r);
    while (now > x) change(now--, l, r);
    while (now < x) change(++now, l, r);
    int k = 1;
    while (sum[k] != 0) k++;
    res[q[i].id] = k;
  }
  for (int i = 1; i <= numq; i++) {
    printf("%d\n", res[i]);
  }
}
int main() {
  scanf("%d%d", &n, &m);
  block = 2000;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    xx[++num] = a[i];
  }
  for (int i = 1; i <= m; i++) {
    int d, x, y;
    scanf("%d%d%d", &d, &x, &y);
    if (d == 1) {
      numq++;
      q[numq] = Query(x, y, numc, numq);
    } else {
      numc++;
      c[numc] = Change(x, y);
      xx[++num] = y;
    }
  }
  sort(xx + 1, xx + 1 + num);
  num = unique(xx + 1, xx + 1 + num) - xx;
  for (int i = 1; i <= n; i++) {
    a[i] = lower_bound(xx + 1, xx + 1 + num, a[i]) - xx;
  }
  for (int i = 1; i <= numc; i++) {
    c[i].y = lower_bound(xx + 1, xx + 1 + num, c[i].y) - xx;
  }
  sort(q + 1, q + 1 + numq, cmp);
  solve();
  return 0;
}