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() {
  register int x = 0, t = 1;
  register char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') t = -1, ch = getchar();
  while (ch <= '9' && ch >= '0') x = x * 10 + ch - 48, ch = getchar();
  return x * t;
}
struct Event {
  int id;
  int l, r, blk;
  int lst;
} Q[200000], P[200000];
int ans[200000];
int S[200000 << 1], ss, n, m, a[200000], b[200000], blk = 3000, tot, q;
int sum[200000], Sum[200000];
int Blk[200000];
bool cmp(Event a, Event b) {
  if (a.blk != b.blk) return a.blk < b.blk;
  if ((a.r - 1) / blk != (b.r - 1) / blk)
    return (a.r - 1) / blk < (b.r - 1) / blk;
  return a.lst < b.lst;
}
void Change(int num, int w) {
  Sum[sum[num]]--;
  if (Sum[sum[num]] == 0) Blk[(Sum[sum[num]] - 1) / 500]--;
  sum[num] += w;
  Sum[sum[num]]++;
  if (Sum[sum[num]] == 1) Blk[(Sum[sum[num]] - 1) / 500]++;
}
int GetAns() {
  for (int i = 0;; ++i) {
    if (Blk[i] == blk) continue;
    for (int j = 1; j <= blk; ++j)
      if (!Sum[i * blk + j]) return i * blk + j;
  }
}
void Modify(int st, int now, int l, int r) {
  if (st == now) return;
  if (now < st)
    for (int i = now + 1; i <= st; ++i) {
      a[P[i].l] = P[i].r;
      if (P[i].l >= l && P[i].l <= r) {
        Change(P[i].lst, -1);
        Change(P[i].r, 1);
      }
    }
  else
    for (int i = now; i > st; --i) {
      a[P[i].l] = P[i].lst;
      if (P[i].l >= l && P[i].l <= r) {
        Change(P[i].r, -1);
        Change(P[i].lst, 1);
      }
    }
}
void Work(int pos, int w) { Change(a[pos], w); }
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; ++i) b[i] = a[i] = read(), S[++ss] = a[i];
  for (int i = 1; i <= m; ++i) {
    int opt = read(), l = read(), r = read();
    if (opt == 1) {
      Q[++q] = (Event){q, l, r, (l - 1) / blk, tot};
    } else {
      P[++tot] = (Event){tot, l, r, 0, b[l]};
      b[l] = r;
      S[++ss] = r;
    }
  }
  sort(&S[1], &S[ss + 1]);
  ss = unique(&S[1], &S[ss + 1]) - S - 1;
  for (int i = 1; i <= n; ++i) a[i] = lower_bound(&S[1], &S[ss + 1], a[i]) - S;
  for (int i = 1; i <= tot; ++i) {
    P[i].r = lower_bound(&S[1], &S[ss + 1], P[i].r) - S;
    P[i].lst = lower_bound(&S[1], &S[ss + 1], P[i].lst) - S;
  }
  sort(&Q[1], &Q[q + 1], cmp);
  int md = 0, l = 1, r = 0;
  for (int i = 1; i <= q; ++i) {
    while (r < Q[i].r) Work(++r, 1);
    while (l > Q[i].l) Work(--l, 1);
    while (r > Q[i].r) Work(r--, -1);
    while (l < Q[i].l) Work(l++, -1);
    Modify(Q[i].lst, md, l, r);
    md = Q[i].lst;
    ans[Q[i].id] = GetAns();
  }
  for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
  return 0;
}