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>
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
const int maxn = 200003, INF = 0x3f3f3f3f;
int n, m;
int bl[maxn];
struct Q {
  int l, r, id, tim;
  bool operator<(const Q& b) const {
    return bl[l] == bl[b.l]
               ? (bl[r] == bl[b.r] ? (bl[r] & 1 ? tim < b.tim : tim > b.tim)
                                   : (bl[l] & 1 ? r < b.r : r > b.r))
               : l < b.l;
  }
} q[maxn];
struct C {
  int pos, now;
} c[maxn];
int L = 1, R, T, col[maxn], vis[maxn], ans[maxn];
int a[maxn], qcnt, Time;
inline void Upd(int x, int d) { --vis[col[x]], col[x] += d, ++vis[col[x]]; }
inline void Chg(int pos, int& x) {
  if (L <= pos && pos <= R) Upd(a[pos], -1), Upd(x, 1);
  std::swap(a[pos], x);
}
void Mo() {
  for (int i = (1); i <= (qcnt); ++i) {
    while (T < q[i].tim) ++T, Chg(c[T].pos, c[T].now);
    while (T > q[i].tim) Chg(c[T].pos, c[T].now), --T;
    int l = q[i].l, r = q[i].r;
    while (l < L) Upd(a[--L], 1);
    while (l > L) Upd(a[L++], -1);
    while (r < R) Upd(a[R--], -1);
    while (r > R) Upd(a[++R], 1);
    int res = 1;
    while (vis[res]) ++res;
    ans[q[i].id] = res;
  }
}
std::unordered_map<int, int> ha;
int tot;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  const int sz = pow(n, 2.0 / 3);
  for (int i = (1); i <= (n); ++i) {
    cin >> a[i], bl[i] = (i - 1) / sz + 1;
    if (ha[a[i]])
      a[i] = ha[a[i]];
    else
      a[i] = ha[a[i]] = ++tot;
  }
  for (int i = (1); i <= (m); ++i) {
    int opt, x, y;
    cin >> opt >> x >> y;
    if (opt & 1)
      q[++qcnt] = (Q){x, y, qcnt, Time};
    else {
      if (ha[y])
        y = ha[y];
      else
        y = ha[y] = ++tot;
      c[++Time] = (C){x, y};
    }
  }
  std::sort(q + 1, q + qcnt + 1);
  Mo();
  for (int i = (1); i <= (qcnt); ++i) cout << ans[i] << '\n';
  return 0;
}