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 N = 200005;
int n, qt, a[N], opt, x, y, cnt, Q, ans[N], block, c[N], ct[N], d[N], tot;
struct qry {
  int l, r, p, id;
} q[N];
struct note {
  int x, y, lst;
} b[N];
bool cmp(qry x, qry y) {
  if (x.l / block != y.l / block) return x.l / block < y.l / block;
  if (x.r / block != y.r / block) return x.r / block < y.r / block;
  return x.p < y.p;
}
void del(int x) {
  int t = a[x];
  c[ct[t]]--;
  ct[t]--;
  c[ct[t]]++;
}
void ins(int x) {
  int t = a[x];
  c[ct[t]]--;
  ct[t]++;
  c[ct[t]]++;
}
int main() {
  scanf("%d%d", &n, &qt);
  block = (int)std::pow(n, 2 * 1.0 / 3) + 1;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), d[++tot] = a[i];
  for (int i = 1; i <= qt; i++) {
    scanf("%d%d%d", &opt, &x, &y);
    if (opt == 1)
      q[++Q] = {x, y, cnt, Q};
    else
      b[++cnt] = {x, y, 0}, d[++tot] = y;
  }
  std::sort(d + 1, d + tot + 1);
  tot = std::unique(d + 1, d + tot + 1) - d - 1;
  for (int i = 1; i <= n; i++)
    a[i] = std::lower_bound(d + 1, d + tot + 1, a[i]) - d;
  for (int i = 1; i <= cnt; i++)
    b[i].y = std::lower_bound(d + 1, d + tot + 1, b[i].y) - d;
  std::sort(q + 1, q + Q + 1, cmp);
  int pl = 0, pr = 0, p = 0;
  for (int i = 1; i <= Q; i++) {
    qry t = q[i];
    while (p < t.p) {
      p++;
      int x = b[p].x;
      if (x >= pl && x <= pr) del(x);
      b[p].lst = a[x], a[x] = b[p].y;
      if (x >= pl && x <= pr) ins(x);
    }
    while (p > t.p) {
      int x = b[p].x;
      if (x >= pl && x <= pr) del(x);
      a[x] = b[p].lst;
      if (x >= pl && x <= pr) ins(x);
      p--;
    }
    while (pl < t.l) del(pl++);
    while (pl > t.l) ins(--pl);
    while (pr > t.r) del(pr--);
    while (pr < t.r) ins(++pr);
    int lim = (int)sqrt(2 * (t.r - t.l + 1)) + 1;
    for (int j = 1; j <= lim; j++)
      if (!c[j]) {
        ans[t.id] = j;
        break;
      }
  }
  for (int i = 1; i <= Q; i++) printf("%d ", ans[i]);
}