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 SZ1 = 2000, SZ2 = 50, MAXN = 1e5 + 10;
int a[MAXN], oa[MAXN], cnt[2 * MAXN], cntcnt[MAXN], ans[MAXN], n, q;
int Q, L, R;
vector<array<int, 3>> qs, cqs;
struct qry {
  int idx, prv, l, r;
  bool operator<(const qry &o) const {
    return make_tuple(prv / SZ1, l / SZ1, r) <
           make_tuple(o.prv / SZ1, o.l / SZ1, o.r);
  }
};
vector<qry> queries;
void aL() {
  cntcnt[cnt[oa[L]]]--;
  cnt[oa[L]]--;
  cntcnt[cnt[oa[L]]]++;
  L++;
}
void sL() {
  L--;
  cntcnt[cnt[oa[L]]]--;
  cnt[oa[L]]++;
  cntcnt[cnt[oa[L]]]++;
}
void aR() {
  R++;
  cntcnt[cnt[oa[R]]]--;
  cnt[oa[R]]++;
  cntcnt[cnt[oa[R]]]++;
}
void sR() {
  cntcnt[cnt[oa[R]]]--;
  cnt[oa[R]]--;
  cntcnt[cnt[oa[R]]]++;
  R--;
}
void aQ() {
  oa[cqs[Q][0]] = cqs[Q][2];
  if (L <= cqs[Q][0] && cqs[Q][0] <= R) {
    cntcnt[cnt[cqs[Q][1]]]--;
    cnt[cqs[Q][1]]--;
    cntcnt[cnt[cqs[Q][1]]]++;
    cntcnt[cnt[cqs[Q][2]]]--;
    cnt[cqs[Q][2]]++;
    cntcnt[cnt[cqs[Q][2]]]++;
  }
  Q++;
}
void sQ() {
  Q--;
  oa[cqs[Q][0]] = cqs[Q][1];
  if (L <= cqs[Q][0] && cqs[Q][0] <= R) {
    cntcnt[cnt[cqs[Q][2]]]--;
    cnt[cqs[Q][2]]--;
    cntcnt[cnt[cqs[Q][2]]]++;
    cntcnt[cnt[cqs[Q][1]]]--;
    cnt[cqs[Q][1]]++;
    cntcnt[cnt[cqs[Q][1]]]++;
  }
}
void solve() {
  sort(queries.begin(), queries.end());
  for (auto q : queries) {
    while (L < q.l) aL();
    while (L > q.l) sL();
    while (R < q.r) aR();
    while (R > q.r) sR();
    while (Q < q.prv) aQ();
    while (Q > q.prv) sQ();
    for (int i = 1;; i++) {
      if (cntcnt[i] == 0) {
        ans[q.idx] = i;
        break;
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> q;
  vector<int> all;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    all.push_back(a[i]);
  }
  for (int i = 0; i < q; i++) {
    int t, x, y;
    cin >> t >> x >> y;
    qs.push_back({t, x, y});
    if (t == 2) all.push_back(y);
  }
  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());
  map<int, int> to;
  for (int i = 0; i < all.size(); i++) to[all[i]] = i + 1;
  for (int i = 1; i <= n; i++) {
    a[i] = to[a[i]];
    oa[i] = a[i];
    cnt[a[i]]++;
  }
  int curcq = 0, curaq = 0;
  for (int i = 0; i < q; i++) {
    if (qs[i][0] == 2) {
      qs[i][2] = to[qs[i][2]];
      cqs.push_back({qs[i][1], a[qs[i][1]], qs[i][2]});
      a[qs[i][1]] = qs[i][2];
      curcq++;
    } else
      queries.push_back({curaq++, curcq, qs[i][1], qs[i][2]});
  }
  for (int i = 1; i < 2 * MAXN; i++) cntcnt[cnt[i]]++;
  Q = 0;
  L = 1;
  R = n;
  solve();
  for (int i = 0; i < queries.size(); i++) cout << ans[i] << '\n';
}