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 __SIZE = 1 << 18;
char ibuf[__SIZE], *iS, *iT;
template <typename T>
inline void read(T &x) {
  char ch, t = 0;
  x = 0;
  while (!isdigit(ch = (iS == iT
                            ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                               (iS == iT ? EOF : *iS++))
                            : *iS++)))
    t |= ch == '-';
  while (isdigit(ch))
    x = x * 10 + (ch ^ 48),
    ch = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                      (iS == iT ? EOF : *iS++))
                   : *iS++);
  x = t ? -x : x;
}
inline int read_int() {
  int x;
  return read(x), x;
}
inline long long read_ll() {
  long long x;
  return read(x), x;
}
template <typename T>
inline void chkmin(T &a, T b) {
  a = a < b ? a : b;
}
template <typename T>
inline void chkmax(T &a, T b) {
  a = a > b ? a : b;
}
const int MAXN = 200010;
int sq;
int a[MAXN];
int b[MAXN];
int cnt[MAXN];
int vis[MAXN];
int res[MAXN];
int val[MAXN];
struct Mdf {
  int p, fr, to;
  inline void rd() { p = read_int(), fr = b[p], b[p] = to = read_int(); }
} mdf[MAXN];
struct Qry {
  int l, r, t, id;
  inline void rd(int T, int Id) {
    t = T, id = Id, l = read_int(), r = read_int();
  }
  friend bool operator<(Qry a, Qry b) {
    if (a.t / sq != b.t / sq) return a.t < b.t;
    if (a.l / sq != b.l / sq) return a.l < b.l;
    return a.r < b.r;
  }
} qry[MAXN];
inline void Add(int x) { --vis[cnt[x]], ++cnt[x], ++vis[cnt[x]]; }
inline void Del(int x) { --vis[cnt[x]], --cnt[x], ++vis[cnt[x]]; }
inline void Remove(Mdf x, int L, int R) {
  if (L <= x.p && x.p <= R) Del(x.to), Add(x.fr);
  a[x.p] = x.fr;
}
inline void Insert(Mdf x, int L, int R) {
  if (L <= x.p && x.p <= R) Del(x.fr), Add(x.to);
  a[x.p] = x.to;
}
inline int GetAns() {
  int mex = 1;
  while (vis[mex]) ++mex;
  return mex;
}
int main() {
  int n = read_int(), m = read_int(), Q = 0, M = 0, N = 0;
  sq = pow(n, 0.667);
  for (int i = 1; i <= n; i++) val[++N] = a[i] = b[i] = read_int();
  for (int i = 1; i <= m; i++) {
    int op = read_int();
    if (op == 1)
      ++Q, qry[Q].rd(M, Q);
    else
      ++M, mdf[M].rd(), val[++N] = mdf[M].to;
  }
  sort(val + 1, val + 1 + N), N = unique(val + 1, val + 1 + N) - val - 1;
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(val + 1, val + 1 + N, a[i]) - val;
  for (int i = 1; i <= M; i++) {
    mdf[i].fr = lower_bound(val + 1, val + 1 + N, mdf[i].fr) - val;
    mdf[i].to = lower_bound(val + 1, val + 1 + N, mdf[i].to) - val;
  }
  sort(qry + 1, qry + 1 + Q);
  vis[0] = 1e9;
  int L = 1, R = 0, T = 0;
  for (int i = 1; i <= Q; i++) {
    Qry q = qry[i];
    while (T > q.t) Remove(mdf[T--], L, R);
    while (T < q.t) Insert(mdf[++T], L, R);
    while (L > q.l) Add(a[--L]);
    while (R < q.r) Add(a[++R]);
    while (L < q.l) Del(a[L++]);
    while (R > q.r) Del(a[R--]);
    res[qry[i].id] = GetAns();
  }
  for (int i = 1; i <= Q; i++) printf("%d\n", res[i]);
  return 0;
}