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, len, tot, top, ans[150000], num, sum[205000], a[150000], cnt[250000],
    d[250000];
struct node {
  int l, r, time, id;
  bool operator<(const node& x) const {
    if ((l / len) == (x.l / len)) {
      if ((r / len) == (x.r / len)) {
        return time < x.time;
      } else {
        return r < x.r;
      }
    } else {
      return l < x.l;
    }
  }
} t[150000];
struct edge {
  int wei, val;
} z[150000];
inline void add(int x, int t) {
  --cnt[sum[x]];
  ++cnt[(sum[x] += t)];
}
inline void up(int i, int k) {
  if (t[i].l <= z[k].wei && z[k].wei <= t[i].r) {
    add(a[z[k].wei], -1);
    add(z[k].val, 1);
  }
  swap(a[z[k].wei], z[k].val);
  return;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), d[i] = a[i];
  len = pow(n, 0.66666);
  for (int i = 1; i <= m; ++i) {
    int opt, x, y;
    scanf("%d%d%d", &opt, &x, &y);
    if (opt == 1) {
      t[++tot].l = x;
      t[tot].r = y;
      t[tot].time = top;
      t[tot].id = tot;
    } else {
      z[++top].wei = x;
      z[top].val = y;
      d[n + top] = y;
    }
  }
  sort(d + 1, d + 1 + n + top);
  int sam = unique(d + 1, d + 1 + n + top) - d - 1;
  for (int i = 1; i <= top; ++i) {
    z[i].val = lower_bound(d + 1, d + 1 + sam, z[i].val) - d;
  }
  for (int i = 1; i <= n; ++i) a[i] = lower_bound(d + 1, d + 1 + sam, a[i]) - d;
  sort(t + 1, t + 1 + tot);
  int l = t[1].l;
  int r = l - 1, tim = 0;
  for (int i = 1; i <= tot; ++i) {
    while (l < t[i].l) add(a[l++], -1);
    while (t[i].l < l) add(a[--l], 1);
    while (r < t[i].r) add(a[++r], 1);
    while (r > t[i].r) add(a[r--], -1);
    while (tim < t[i].time) up(i, ++tim);
    while (tim > t[i].time) up(i, tim--);
    for (ans[t[i].id] = 1; cnt[ans[t[i].id]] > 0; ++ans[t[i].id])
      ;
  }
  for (int i = 1; i <= tot; ++i) {
    printf("%d\n", ans[i]);
  }
  return 0;
}