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 maxN = 2e5 + 10;
int BLOCK_SIZE;
void Dbg() { puts(""); }
template <typename T, typename... Args>
void Dbg(T x, Args... args) {
  cout << x << ' ';
  Dbg(args...);
}
template <typename T>
inline void readInt(T &x) {
  char c = getchar();
  x = 0;
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
}
template <typename T, typename... Args>
inline void readInt(T &x, Args &...args) {
  readInt(x), readInt(args...);
}
template <typename T>
inline void readChar(T &x) {
  char c = getchar();
  while (c == '\n' || c == ' ') c = getchar();
  x = c;
}
struct Query {
  int L, R, id, tm, bl, br;
  Query() {}
  Query(int _L, int _R, int _id, int _tm) : L(_L), R(_R), id(_id), tm(_tm) {
    bl = L / BLOCK_SIZE;
    br = R / BLOCK_SIZE;
  }
  bool operator<(const Query &rhs) const {
    return bl == rhs.bl ? (br == rhs.br ? tm < rhs.tm : br < rhs.br)
                        : bl < rhs.bl;
  }
} Q[maxN];
struct Change {
  int pos, now, pre;
} C[maxN];
int n, q, sz, tmp, Cidx, Qidx;
int qs[maxN], num[maxN], cnt[maxN], ans[maxN], now[maxN];
map<int, int> xs;
inline int getId(int x) {
  if (!xs.count(x)) xs[x] = ++sz;
  return xs[x];
}
inline void revise(int x, int d) {
  if (num[x] > 0) cnt[num[x]]--;
  num[x] += d;
  if (num[x] > 0) cnt[num[x]]++;
}
inline void update(int x, int d, int L, int R) {
  if (L <= x && x <= R) revise(qs[x], -1), revise(d, 1);
  qs[x] = d;
}
int main() {
  scanf("%d%d", &n, &q), BLOCK_SIZE = pow(n, 0.666666);
  for (int i = 1; i <= n; i++)
    scanf("%d", qs + i), now[i] = qs[i] = getId(qs[i]);
  for (int i = 1, op, a, b; i <= q; i++) {
    scanf("%d%d%d", &op, &a, &b);
    if (op == 1)
      Q[++Qidx] = Query(a, b, Qidx, Cidx);
    else
      b = getId(b), C[++Cidx] = {a, b, now[a]}, now[a] = b;
  }
  sort(Q + 1, Q + 1 + Qidx);
  for (int i = 1, L = 1, R = 0, T = 0; i <= Qidx; i++) {
    Query &q = Q[i];
    int x = 1;
    while (T < q.tm) ++T, update(C[T].pos, C[T].now, L, R);
    while (T > q.tm) update(C[T].pos, C[T].pre, L, R), T--;
    while (L < q.L) revise(qs[L++], -1);
    while (L > q.L) revise(qs[--L], 1);
    while (R < q.R) revise(qs[++R], 1);
    while (R > q.R) revise(qs[R--], -1);
    while (cnt[x]) x++;
    ans[q.id] = x;
  }
  for (int i = 1; i <= Qidx; i++) printf("%d\n", ans[i]);
}