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;
inline int read() {
  int x = 0;
  bool op = false;
  char c = getchar();
  while (!isdigit(c)) op |= (c == '-'), c = getchar();
  while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
const int N = 100010;
int n, Q, cnt_q, cnt_r, cnt_num, T, sum;
int a[N], lsh[N * 2], cntnum[N * 2], cnt[N * 2], ans[N];
struct Query {
  int lt, rt, id;
  int tim;
  Query(int lt = 0, int rt = 0, int id = 0, int tim = 0)
      : lt(lt), rt(rt), id(id), tim(tim) {}
} q[N];
struct Replace {
  int pos, num;
  Replace(int pos = 0, int num = 0) : pos(pos), num(num) {}
} c[N];
void init() {
  sort(lsh, lsh + cnt_num);
  int size = unique(lsh, lsh + cnt_num) - lsh;
  for (int i = 1; i <= n; i++) {
    a[i] = lower_bound(lsh, lsh + size, a[i]) - lsh;
  }
  for (int i = 1; i <= cnt_r; i++) {
    c[i].num = lower_bound(lsh, lsh + size, c[i].num) - lsh;
  }
  return;
}
void In() {
  n = read();
  Q = read();
  for (int i = 1; i <= n; i++) {
    lsh[cnt_num++] = a[i] = read();
  }
  for (int i = 1; i <= Q; i++) {
    int op = read();
    if (op == 1) {
      int l = read(), r = read();
      cnt_q++;
      q[cnt_q] = Query(l, r, cnt_q, cnt_r);
    } else {
      cnt_r++;
      c[cnt_r].pos = read();
      lsh[cnt_num++] = c[cnt_r].num = read();
    }
  }
  init();
  return;
}
bool cmp(Query a, Query b) {
  if (a.lt / T != b.lt / T)
    return a.lt < b.lt;
  else if (a.rt / T != b.rt / T)
    return a.rt < b.rt;
  return a.tim < b.tim;
}
void add(int x) {
  cnt[cntnum[a[x]]]--;
  cnt[cntnum[a[x]] + 1]++;
  cntnum[a[x]]++;
  return;
}
void del(int x) {
  cnt[cntnum[a[x]]]--;
  cnt[cntnum[a[x]] - 1]++;
  cntnum[a[x]]--;
  return;
}
void modify(int cur, int i) {
  if (c[cur].pos >= q[i].lt && c[cur].pos <= q[i].rt) {
    del(c[cur].pos);
    int tmp = a[c[cur].pos];
    a[c[cur].pos] = c[cur].num;
    add(c[cur].pos);
    a[c[cur].pos] = tmp;
  }
  swap(a[c[cur].pos], c[cur].num);
  return;
}
void Solve() {
  T = pow(n, 0.6666);
  sort(q + 1, q + 1 + cnt_q, cmp);
  int cur = 0, x = 1, y = 0;
  for (int i = 1; i <= cnt_q; i++) {
    int qx = q[i].lt, qy = q[i].rt;
    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 (q[i].tim > cur) {
      cur++;
      modify(cur, i);
    }
    while (q[i].tim < cur) {
      modify(cur, i);
      cur--;
    }
    for (int j = 0;; j++) {
      if (cnt[j] == 0) {
        ans[q[i].id] = j;
        break;
      }
    }
  }
  return;
}
void Print() {
  for (int i = 1; i <= cnt_q; i++) {
    printf("%d\n", ans[i]);
  }
  return;
}
int main() {
  In();
  Solve();
  Print();
  return 0;
}