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 MAXN = 3 * 100 * 1000 + 17;
int n, q, S, a[MAXN], ans[MAXN], cnt, m, b[MAXN], c[MAXN], st = 1, en, tnow;
vector<int> num[MAXN];
pair<int, int> upd[MAXN];
pair<pair<int, int>, pair<int, int> > qr[MAXN];
bool cmp_mo(pair<pair<int, int>, pair<int, int> > A,
            pair<pair<int, int>, pair<int, int> > B) {
  if (A.first.first / S != B.first.first / S)
    return A.first.first < B.first.first;
  if (A.first.second / S != B.first.second / S)
    return A.first.second < B.first.second;
  return A.second.first < B.second.first;
}
void compress() {
  vector<int> all;
  for (int i = 1; i <= n; i++) all.push_back(a[i]);
  for (int i = 1; i <= cnt; i++) all.push_back(upd[i].second);
  sort(all.begin(), all.end());
  all.resize(unique(all.begin(), all.end()) - all.begin());
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(all.begin(), all.end(), a[i]) - all.begin() + 1;
  for (int i = 1; i <= cnt; i++)
    upd[i].second =
        lower_bound(all.begin(), all.end(), upd[i].second) - all.begin() + 1;
}
void change(int x, int val) {
  if (x == 0) return;
  b[c[x]]--;
  c[x] += val;
  b[c[x]]++;
}
void undo(int updNUM) {
  int x = upd[updNUM].first;
  if (st <= x && x <= en) change(num[x].back(), -1);
  num[x].pop_back();
  if (st <= x && x <= en) change(num[x].back(), 1);
}
void do_upd(int updNUM) {
  int x = upd[updNUM].first, val = upd[updNUM].second;
  if (st <= x && x <= en) change(num[x].back(), -1);
  num[x].push_back(val);
  if (st <= x && x <= en) change(num[x].back(), 1);
}
void add(int x, int val) { change(num[x].back(), val); }
int get() {
  for (int i = 1;; i++)
    if (!b[i]) return i;
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> q;
  S = cbrt(n) * cbrt(n);
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= q; i++) {
    int t, x, y;
    cin >> t >> x >> y;
    if (t == 2)
      upd[++cnt] = {x, y};
    else {
      ++m;
      qr[m] = {{x, y}, {cnt, m}};
    }
  }
  compress();
  for (int i = 1; i <= n; i++) num[i].push_back(a[i]);
  sort(qr + 1, qr + m + 1, cmp_mo);
  for (int i = 1; i <= m; i++) {
    while (tnow < qr[i].second.first) do_upd(++tnow);
    while (tnow > qr[i].second.first) undo(tnow--);
    while (en < qr[i].first.second) add(++en, 1);
    while (en > qr[i].first.second) add(en--, -1);
    while (st < qr[i].first.first) add(st++, -1);
    while (st > qr[i].first.first) add(--st, 1);
    ans[qr[i].second.second] = get();
  }
  for (int i = 1; i <= m; i++) cout << ans[i] << endl;
  return 0;
}