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")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
struct node {
  int t, i, l, r;
  node(int t, int i, int l, int r) {
    this->t = t;
    this->i = i;
    this->l = l;
    this->r = r;
  }
};
vector<int> up;
vector<node> qr;
map<int, int> m;
int sz[100100], cnt[100100 * 2], ans[100100], idx[100100], fc = 0, l, r, t;
vector<int> a[100100];
int get(int p) {
  if (m.count(p)) return m[p];
  return m[p] = ++fc;
}
inline bool compare(node a, node b) {
  if ((a.t / 2155) == (b.t / 2155)) {
    if ((a.l / 2155) == (b.l / 2155)) return a.r < b.r;
    return (a.l / 2155) < (b.l / 2155);
  }
  return (a.t / 2155) < (b.t / 2155);
}
inline void update(int pos) {
  int x = a[pos][idx[pos] + 1];
  if (pos >= l and pos <= r) {
    int y = a[pos][idx[pos]];
    sz[cnt[y]]--;
    cnt[y]--;
    sz[cnt[y]]++;
    sz[cnt[x]]--;
    cnt[x]++;
    sz[cnt[x]]++;
  }
  idx[pos]++;
}
inline void remove(int pos) {
  int x = a[pos][idx[pos]];
  idx[pos]--;
  if (pos >= l and pos <= r) {
    int y = a[pos][idx[pos]];
    sz[cnt[y]]--;
    cnt[y]++;
    sz[cnt[y]]++;
    sz[cnt[x]]--;
    cnt[x]--;
    sz[cnt[x]]++;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  sz[0] = 100100;
  int n, q, c;
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> c;
    a[i].push_back(get(c));
  }
  for (int i = 0; i < q; i++) {
    cin >> t >> l >> r;
    if (t == 1)
      qr.push_back(node(up.size(), i, l, r));
    else
      up.push_back(l), a[l].push_back(get(r));
  }
  t = 0, l = 1, r = 0;
  sort(qr.begin(), qr.end(), compare);
  for (auto& u : qr) {
    while (u.t > t) update(up[t++]);
    while (u.t < t) remove(up[--t]);
    while (l > u.l) {
      l--;
      int y = a[l][idx[l]];
      sz[cnt[y]]--;
      cnt[y]++;
      sz[cnt[y]]++;
    }
    while (l < u.l) {
      int y = a[l][idx[l]];
      sz[cnt[y]]--;
      cnt[y]--;
      sz[cnt[y]]++;
      l++;
    }
    while (r > u.r) {
      int y = a[r][idx[r]];
      sz[cnt[y]]--;
      cnt[y]--;
      sz[cnt[y]]++;
      r--;
    }
    while (r < u.r) {
      r++;
      int y = a[r][idx[r]];
      sz[cnt[y]]--;
      cnt[y]++;
      sz[cnt[y]]++;
    }
    while (sz[ans[u.i]]) ans[u.i]++;
  }
  for (int i = 0; i < q; i++)
    if (ans[i]) cout << ans[i] << '\n';
  return 0;
}