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;
int res[200005], n, q;
long long memo[2 * 200005];
long long cnt[200005];
long long pre[200005];
long long x, t, y, s;
long long a[200005];
vector<long long> Value;
void input() {
  freopen(
      "Machine learning"
      ".inp",
      "r", stdin);
  freopen(
      "Machine learning"
      ".out",
      "w", stdout);
}
struct Up {
  long long idx, val;
};
struct Query {
  long long idx, l, r;
  long long tim;
};
vector<Up> update;
vector<Query> query;
void Boost() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
inline bool cmp(Query &a, Query &b) {
  if (a.tim / s == b.tim / s) {
    if (a.l / s != b.l / s) {
      return a.l < b.l;
    }
    return a.r < b.r;
  }
  return a.tim / s < b.tim / s;
}
inline void up(int i) {
  cnt[memo[a[i]]]--;
  memo[a[i]]++;
  cnt[memo[a[i]]]++;
}
inline void del(int i) {
  cnt[memo[a[i]]]--;
  memo[a[i]]--;
  cnt[memo[a[i]]]++;
}
int main() {
  Boost();
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    Value.push_back(a[i]);
  }
  s = pow(n, 2. / 3.);
  int d = 0, dd = 0;
  update.push_back({0, 0});
  for (int i = 1; i <= q; ++i) {
    cin >> t >> x >> y;
    if (t == 2) {
      d++;
      update.push_back({x, y});
      Value.push_back(y);
    } else {
      query.push_back({dd, x, y, d});
      dd++;
    }
  }
  sort(Value.begin(), Value.end());
  long long it = unique(Value.begin(), Value.end()) - Value.begin();
  Value.resize(it);
  for (auto &i : update)
    i.val = lower_bound(Value.begin(), Value.end(), i.val) - Value.begin() + 1;
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(Value.begin(), Value.end(), a[i]) - Value.begin() + 1;
  sort(query.begin(), query.end(), cmp);
  int cur_l = query[0].l;
  int cur_r = query[0].l - 1;
  int cur_time = 0;
  for (int i = 0; i < dd; i++) {
    while (cur_time < query[i].tim) {
      cur_time++;
      int pos = update[cur_time].idx;
      pre[cur_time] = a[pos];
      if (pos >= cur_l && pos <= cur_r)
        del(pos), a[pos] = update[cur_time].val, up(pos);
      a[pos] = update[cur_time].val;
    }
    while (cur_time > query[i].tim) {
      int pos = update[cur_time].idx;
      if (pos >= cur_l && pos <= cur_r)
        del(pos), a[pos] = pre[cur_time], up(pos);
      a[pos] = pre[cur_time];
      cur_time--;
    }
    while (cur_l < query[i].l) del(cur_l++);
    while (cur_l > query[i].l) up(--cur_l);
    while (cur_r > query[i].r) del(cur_r--);
    while (cur_r < query[i].r) up(++cur_r);
    int j = 1;
    while (cnt[j] != 0) j++;
    res[query[i].idx] = j;
  }
  for (int i = 0; i < dd; i++) cout << res[i] << '\n';
  return 0;
}