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 LL = 1 << 19;
char ibuf[LL], *ie = ibuf + LL, *ip = ie - 1;
inline char nc(void) {
  if (++ip == ie)
    if (fread(ip = ibuf, 1, LL, stdin))
      ;
  return *ip;
}
inline int read(void) {
  char opt;
  int flag = 1, res = 0;
  while ((opt = nc()) < '0')
    if (opt == '-') flag = -1;
  while (opt >= '0') {
    res = (res << 3) + (res << 1) + opt - '0';
    opt = nc();
  }
  return res * flag;
}
int a[200001], belong[200001], n, m, qtot, stot, ans, Ans[200001], sum[200001],
    sz, ss[200001], tot, mxx, t[200001];
inline char gc(void) {
  char opt = nc();
  while (opt != 'Q' && opt != 'R') opt = nc();
  return opt;
}
struct Que {
  int l, r, time, pos;
  inline char operator<(Que a) const {
    if (belong[l] == belong[a.l])
      return belong[r] == belong[a.r]
                 ? (((belong[r] ^ belong[l]) & 1) ? time < a.time
                                                  : time > a.time)
             : (belong[l] & 1) ? r < a.r
                               : r > a.r;
    else {
      return l < a.l;
    }
  }
} q[200001];
struct Cmd {
  int v, x, y;
} s[200001];
inline void Add(int x, int v) {
  --ss[sum[x]];
  ++ss[sum[x] += v];
}
inline void Read(void) {
  int i, x, y;
  char opt;
  tot = n = read();
  m = read();
  for (i = 1; i <= n; ++i) mxx = max(mxx, t[i] = a[i] = read());
  for (i = 1; i <= m; ++i) {
    opt = read(), x = read(), t[++tot] = y = read();
    if (opt == 1)
      q[++qtot] = {x, y, stot, qtot};
    else
      s[++stot] = {x, y, a[x]}, a[x] = y;
  }
  sort(t + 1, t + tot + 1);
  tot = unique(t + 1, t + tot + 1) - t - 1;
  for (i = 1; i <= n; ++i) a[i] = lower_bound(t + 1, t + tot + 1, a[i]) - t;
  for (i = 1; i <= stot; ++i) {
    s[i].x = lower_bound(t + 1, t + tot + 1, s[i].x) - t;
    s[i].y = lower_bound(t + 1, t + tot + 1, s[i].y) - t;
  }
  sz = pow(n, 2. / 3);
  for (i = 1; i <= n; ++i) belong[i] = (i - 1) / sz + 1;
  sort(q + 1, q + qtot + 1);
}
inline void Solve(void) {
  int i, j, l = 1, r = 0, now;
  for (i = 1, l = 1, r = 0, now = stot; i <= qtot; ++i) {
    while (r < q[i].r) Add(a[++r], 1);
    while (r > q[i].r) Add(a[r--], -1);
    while (l < q[i].l) Add(a[l++], -1);
    while (l > q[i].l) Add(a[--l], 1);
    while (now < q[i].time) {
      ++now;
      if (l <= s[now].v && s[now].v <= r) {
        Add(a[s[now].v], -1);
        a[s[now].v] = s[now].x;
        Add(a[s[now].v], 1);
      } else
        a[s[now].v] = s[now].x;
    }
    while (now > q[i].time) {
      if (l <= s[now].v && s[now].v <= r) {
        Add(a[s[now].v], -1);
        a[s[now].v] = s[now].y;
        Add(a[s[now].v], 1);
      } else
        a[s[now].v] = s[now].y;
      --now;
    }
    for (j = 1; j <= n; ++j)
      if (!ss[j]) {
        Ans[q[i].pos] = j;
        break;
      }
  }
  for (i = 1; i <= qtot; ++i) printf("%d\n", Ans[i]);
}
int main(void) {
  Read();
  Solve();
  return 0;
}