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;
constexpr int MAXN = 133334;
template <typename T>
inline void read(T& x, T f = 1, char ch = getchar()) {
  x = 0;
  while (!isdigit(ch)) f = (ch == '-') ? -1 : 1, ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
  x *= f;
}
int n, m, cntQ, cntR, base;
int col[MAXN], belong[MAXN], cnt[MAXN << 3], ans[MAXN], C[MAXN];
struct Query {
  int l, r, id, tim;
  friend inline bool operator<(const Query& lhs, const Query& rhs) {
    if (belong[lhs.l] != belong[rhs.l]) return lhs.l < rhs.l;
    if (belong[lhs.r] != belong[rhs.r]) return lhs.r < rhs.r;
    return lhs.tim < rhs.tim;
  }
} q[MAXN];
struct Change {
  int pos, col;
} chg[MAXN];
inline void discrete() {
  vector<int> vec;
  for (int i = 1; i <= n; i++) vec.push_back(col[i]);
  for (int i = 1; i <= cntR; i++) vec.push_back(chg[i].col);
  sort(vec.begin(), vec.end());
  auto edIt = unique(vec.begin(), vec.end());
  for (int i = 1; i <= n; i++)
    col[i] = lower_bound(vec.begin(), edIt, col[i]) - vec.begin();
  for (int i = 1; i <= cntR; i++)
    chg[i].col = lower_bound(vec.begin(), edIt, chg[i].col) - vec.begin();
}
inline void add(int pos) { --C[cnt[col[pos]]], ++C[++cnt[col[pos]]]; }
inline void del(int pos) { --C[cnt[col[pos]]], ++C[--cnt[col[pos]]]; }
inline void change(int tim, Query& query) {
  if (query.l <= chg[tim].pos && chg[tim].pos <= query.r) {
    --C[cnt[col[chg[tim].pos]]], ++C[--cnt[col[chg[tim].pos]]];
    --C[cnt[chg[tim].col]], ++C[++cnt[chg[tim].col]];
  }
  swap(chg[tim].col, col[chg[tim].pos]);
}
int main() {
  read(n), read(m), base = pow(n, 0.66);
  for (int i = 1; i <= n; i++) cin >> col[i], belong[i] = i / base;
  while (m--) {
    int opt;
    read(opt);
    if (opt == 1) {
      read(q[++cntQ].l), read(q[cntQ].r);
      q[cntQ].id = cntQ, q[cntQ].tim = cntR;
    } else
      read(chg[++cntR].pos), read(chg[cntR].col);
  }
  discrete();
  sort(q + 1, q + cntQ + 1);
  int l = 1, r = 0, tim = 0;
  for (int i = 1; i <= cntQ; i++) {
    while (r < q[i].r) add(++r);
    while (r > q[i].r) del(r--);
    while (l < q[i].l) del(l++);
    while (l > q[i].l) add(--l);
    while (tim < q[i].tim) change(++tim, q[i]);
    while (tim > q[i].tim) change(tim--, q[i]);
    for (ans[q[i].id] = 1; C[ans[q[i].id]] != 0; ans[q[i].id]++)
      ;
  }
  for (int i = 1; i <= cntQ; i++) printf("%d\n", ans[i]);
  return 0;
}