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>
char nc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
int rd() {
  int x = 0;
  char c = nc();
  while (!isdigit(c)) c = nc();
  while (isdigit(c)) x = x * 10 + c - '0', c = nc();
  return x;
}
const int N = 1e5 + 3;
struct Quer {
  int l, r, t, id;
} Q[N];
struct Chan {
  int pos, val;
} C[N];
int qcnt, ccnt;
int b[N * 2 + 1], bcnt;
int n, m, a[N], B, belong[N];
bool cmp(const Quer& x, const Quer& y) {
  return belong[x.l] ^ belong[y.l]   ? x.l < y.l
         : belong[x.r] ^ belong[y.r] ? x.r < y.r
                                     : x.t < y.t;
}
namespace Block {
int B, belong[N], lim[N], sum[N], a[N];
void init() {
  B = sqrt(n);
  for (int i = 1; i <= n; ++i) belong[i] = i / B, ++lim[belong[i]];
}
void ins(int x, int v) { sum[belong[x]] += v, a[x] += v; }
int mex() {
  int l = 1;
  while (sum[belong[l]] == lim[belong[l]]) l += lim[belong[l]];
  while (a[l]) ++l;
  return l;
}
}  // namespace Block
int num[N * 2 + 1], book[N], ans[N];
void ins(int x) {
  --book[num[x]];
  if (!book[num[x]]) Block ::ins(num[x], -1);
  ++num[x];
  if (!book[num[x]]) Block ::ins(num[x], 1);
  ++book[num[x]];
}
void del(int x) {
  --book[num[x]];
  if (!book[num[x]]) Block ::ins(num[x], -1);
  --num[x];
  if (!book[num[x]]) Block ::ins(num[x], 1);
  ++book[num[x]];
}
void upd(int x, int t) {
  if (Q[x].l <= C[t].pos && C[t].pos <= Q[x].r) {
    del(a[C[t].pos]);
    ins(C[t].val);
  }
  std ::swap(a[C[t].pos], C[t].val);
}
int main() {
  n = rd(), m = rd();
  B = pow(n, 0.666666);
  if (!B) B = 1;
  for (int i = 1; i <= n; ++i) a[i] = rd(), b[++bcnt] = a[i], belong[i] = i / B;
  while (m--) {
    int op = rd();
    if (op == 1) {
      ++qcnt;
      Q[qcnt].l = rd(), Q[qcnt].r = rd(), Q[qcnt].t = ccnt, Q[qcnt].id = qcnt;
    }
    if (op == 2) {
      ++ccnt;
      C[ccnt].pos = rd(), C[ccnt].val = rd();
      b[++bcnt] = C[ccnt].val;
    }
  }
  std ::sort(b + 1, b + 1 + bcnt);
  bcnt = std ::unique(b + 1, b + 1 + bcnt) - b - 1;
  for (int i = 1; i <= n; ++i)
    a[i] = std ::lower_bound(b + 1, b + 1 + bcnt, a[i]) - b;
  for (int i = 1; i <= ccnt; ++i)
    C[i].val = std ::lower_bound(b + 1, b + 1 + bcnt, C[i].val) - b;
  Block ::init();
  std ::sort(Q + 1, Q + 1 + qcnt, cmp);
  for (int i = 1, l = 1, r = 0, t = 0; i <= qcnt; ++i) {
    while (r < Q[i].r) ins(a[++r]);
    while (r > Q[i].r) del(a[r--]);
    while (l < Q[i].l) del(a[l++]);
    while (l > Q[i].l) ins(a[--l]);
    while (t < Q[i].t) upd(i, ++t);
    while (t > Q[i].t) upd(i, t--);
    ans[Q[i].id] = Block ::mex();
  }
  for (int i = 1; i <= qcnt; ++i) std ::cout << ans[i] << '\n';
  return 0;
}