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;
using ll = long long;
const int MAXN = 1e5 + 7;
int n, q;
const int INSERT = 2, GET = 1;
struct Query {
  int l, r, t, index;
};
Query queries[MAXN];
vector<int> prv[MAXN];
int arr[MAXN];
int ans[MAXN];
struct Mex_SQRT {
  const int BLOCK_SIZE = 322;
  int blocks[MAXN]{};
  int arr[MAXN * 2]{};
  void insert(int x, int what) {
    x = min(MAXN - 1, x);
    assert(x >= 0);
    if (arr[x] > 0 && arr[x] + what == 0) blocks[x]--;
    if (arr[x] == 0 && arr[x] + what > 0) blocks[x]++;
    arr[x] += what;
  }
  int get() {
    for (int block = 0; block < MAXN; block++)
      for (int i = 0; i < BLOCK_SIZE && i + BLOCK_SIZE * block < MAXN; i++)
        if (arr[i + block * BLOCK_SIZE] == 0) return i + block * BLOCK_SIZE;
    assert(0);
  }
};
struct Hist {
  int hist[MAXN]{};
  Mex_SQRT have{};
  explicit Hist(int mx) {
    hist[0] = mx + 1;
    have.insert(0, mx + 1);
  }
  void insert(int x, int who) {
    have.insert(hist[x], -1);
    hist[x] += who;
    have.insert(hist[x], 1);
  }
  int get() { return have.get(); }
};
pair<int, int> inserts[MAXN];
int solve() {
  if (!(cin >> n >> q)) return 1;
  vector<int> to_sort;
  to_sort.reserve(n + q + 1);
  to_sort.push_back(0);
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
    to_sort.push_back(arr[i]);
  }
  int cnt = 0, cnt1 = 0;
  for (int i = 0; i < q; i++) {
    int type, l, r;
    cin >> type >> l >> r;
    l--;
    if (type == INSERT) {
      inserts[cnt++] = {l, r};
      to_sort.push_back(r);
    } else {
      queries[cnt1] = {l, r, cnt, cnt1};
      cnt1++;
    }
  }
  q = cnt1;
  sort((to_sort).begin(), (to_sort).end());
  to_sort.erase(unique((to_sort).begin(), (to_sort).end()), to_sort.end());
  for (int i = 0; i < n; i++)
    arr[i] = (int)(lower_bound((to_sort).begin(), (to_sort).end(), arr[i]) -
                   to_sort.begin());
  for (int i = 0; i < cnt; i++)
    inserts[i].second = (int)(lower_bound((to_sort).begin(), (to_sort).end(),
                                          inserts[i].second) -
                              to_sort.begin());
  const int BLOCK_SIZE = cbrtl(1LL * n * n);
  sort(queries, queries + cnt1, [&](const Query &a, const Query &b) {
    if (a.t / BLOCK_SIZE != b.t / BLOCK_SIZE)
      return a.t / BLOCK_SIZE < b.t / BLOCK_SIZE;
    if (a.l / BLOCK_SIZE != b.l / BLOCK_SIZE)
      return a.l / BLOCK_SIZE < b.l / BLOCK_SIZE;
    return a.r < b.r;
  });
  int l = 0, r = 0;
  int t = 0;
  Hist histogram((int)((to_sort).size()));
  for (int i = 0; i < cnt1; i++) {
    auto &qr = queries[i];
    while (t < qr.t) {
      auto [pos, x] = inserts[t];
      if (l <= pos && pos < r) {
        histogram.insert(arr[pos], -1);
        histogram.insert(x, 1);
      }
      prv[pos].push_back(arr[pos]);
      arr[pos] = x;
      t++;
    }
    while (t > qr.t) {
      --t;
      auto [pos, x] = inserts[t];
      int p = prv[pos].back();
      prv[pos].pop_back();
      if (l <= pos && pos < r) {
        histogram.insert(x, -1);
        histogram.insert(p, 1);
      }
      arr[pos] = p;
    }
    while (r < qr.r) histogram.insert(arr[r++], 1);
    while (l > qr.l) histogram.insert(arr[--l], 1);
    while (l < qr.l) histogram.insert(arr[l++], -1);
    while (r > qr.r) histogram.insert(arr[--r], -1);
    ans[qr.index] = histogram.get();
  }
  for (int i = 0; i < cnt1; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int tests = 1e9;
  for (int i = 1; i <= tests; i++) {
    if (solve()) break;
  }
}