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 string end_mark("^__=end=__^");
int naive(istream& cin, ostream& cout);
int body(istream& cin, ostream& cout);
void cmpNaive() {
  while (true) {
    string s;
    getline(cin, s);
    bool run_body;
    if (s.at(0) == 'Q') {
      return;
    } else if (s.at(0) == 'B') {
      run_body = true;
    } else if (s.at(0) == 'N') {
      run_body = false;
    } else {
      cerr << "Unknown body/naive specifier.\n";
      exit(1);
    }
    string input_s;
    while (true) {
      getline(cin, s);
      if (s == end_mark) break;
      input_s += s;
      input_s += "\n";
    }
    stringstream ss_in(move(input_s));
    stringstream ss_out;
    if (run_body) {
      body(ss_in, ss_out);
    } else {
      naive(ss_in, ss_out);
    }
    cout << ss_out.str() << end_mark << endl;
  }
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);
  body(cin, cout);
  return 0;
}
int naive(istream& cin, ostream& cout) {
  long long int n, q;
  cin >> n >> q;
  vector<long long int> A(n + 1);
  const long long int lim = 110;
  for (long long int i = 1; i <= n; i++) cin >> A[i];
  for (long long int qq = 0; qq < q; qq++) {
    long long int t, b, c;
    cin >> t >> b >> c;
    if (t == 1) {
      vector<long long int> count(lim);
      vector<long long int> csize(lim);
      for (long long int i = b; i <= c; i++) count[A[i]]++;
      for (long long int i = 0; i < lim; i++) csize[count[i]]++;
      for (long long int i = 0; i < lim; i++) {
        if (csize[i] == 0) {
          cout << i << "\n";
          break;
        }
      }
    } else {
      A[b] = c;
    }
  }
  return 0;
}
int body(istream& cin, ostream& cout) {
  std::chrono::steady_clock::time_point begin =
      std::chrono::steady_clock::now();
  long long int n, q;
  cin >> n >> q;
  vector<long long int> A(n);
  for (long long int i = 0; i < n; i++) cin >> A[i];
  vector<long long int> T(q), B(q), C(q);
  for (long long int i = 0; i < q; i++) {
    cin >> T[i] >> B[i] >> C[i];
    if (T[i] == 1) B[i]--;
    if (T[i] == 2) B[i]--;
  }
  map<long long int, long long int> app;
  for (long long int i = 0; i < n; i++) app[A[i]] = 1;
  for (long long int i = 0; i < q; i++)
    if (T[i] == 2) app[C[i]] = 1;
  long long int sz = app.size();
  {
    long long int i = 1;
    for (auto& [a, v] : app) v = i++;
  }
  for (long long int i = 0; i < n; i++) A[i] = app[A[i]];
  for (long long int i = 0; i < q; i++)
    if (T[i] == 2) C[i] = app[C[i]];
  std::chrono::steady_clock::time_point end;
  end = std::chrono::steady_clock::now();
  cerr << "Point1"
       << std::chrono::duration_cast<std::chrono::microseconds>(end - begin)
              .count()
       << "\n";
  using modify_t = tuple<long long int, long long int, long long int>;
  vector<modify_t> modify;
  using q_t = tuple<long long int, long long int, long long int, long long int>;
  vector<q_t> query;
  {
    long long int tm = 0;
    auto AA(A);
    for (long long int i = 0; i < q; i++) {
      if (T[i] == 1)
        query.emplace_back(i, tm, B[i], C[i]);
      else if (T[i] == 2) {
        modify.emplace_back(B[i], AA[B[i]], C[i]);
        AA[B[i]] = C[i];
        tm++;
      }
    }
  }
  end = std::chrono::steady_clock::now();
  cerr << "Point2"
       << std::chrono::duration_cast<std::chrono::microseconds>(end - begin)
              .count()
       << "\n";
  long long int P = max(1LL, llround(pow(double(n), 0.66)));
  cerr << "P = " << P << "\n";
  sort(query.begin(), query.end(), [&](const q_t& q1, const q_t& q2) -> bool {
    const auto& [q_id1, tm1, l1, r1] = q1;
    const auto& [q_id2, tm2, l2, r2] = q2;
    if (tm1 / P != tm2 / P) return tm1 / P < tm2 / P;
    if (l1 / P != l2 / P) return l1 / P < l2 / P;
    return r1 < r2;
  });
  end = std::chrono::steady_clock::now();
  cerr << "Point3"
       << std::chrono::duration_cast<std::chrono::microseconds>(end - begin)
              .count()
       << "\n";
  vector<long long int> count(sz + 1);
  vector<long long int> csize(n + 2);
  long long int l0 = 0;
  long long int r0 = 0;
  long long int tm0 = 0;
  long long int op_count = 0;
  auto mod_x = [&](long long int x, long long int diff) -> void {
    long long int c = count[x];
    csize[c]--;
    csize[c + diff]++;
    count[x] += diff;
  };
  auto inc_x = [&](long long int x) -> void {
    long long int& c = count[x];
    csize[c]--;
    c++;
    csize[c]++;
  };
  auto dec_x = [&](long long int x) -> void {
    long long int& c = count[x];
    csize[c]--;
    c--;
    csize[c]++;
  };
  vector<long long int> ans(q);
  for (const auto& [q_id, tm, l, r] : query) {
    while (r0 < r) {
      inc_x(A[r0]);
      r0++;
      op_count++;
    }
    while (l < l0) {
      l0--;
      inc_x(A[l0]);
      op_count++;
    }
    while (r < r0) {
      r0--;
      dec_x(A[r0]);
      op_count++;
    }
    while (l0 < l) {
      dec_x(A[l0]);
      l0++;
      op_count++;
    }
    while (tm0 < tm) {
      const auto& [idx, old_v, new_v] = modify[tm0];
      assert(A[idx] == old_v);
      A[idx] = new_v;
      if (l <= idx && idx < r) {
        dec_x(old_v);
        inc_x(new_v);
      }
      tm0++;
      op_count++;
    }
    while (tm < tm0) {
      tm0--;
      const auto& [idx, old_v, new_v] = modify[tm0];
      assert(A[idx] == new_v);
      A[idx] = old_v;
      if (l <= idx && idx < r) {
        dec_x(new_v);
        inc_x(old_v);
      }
      op_count++;
    }
    for (long long int i = 1; i < (long long int)csize.size(); i++) {
      if (csize[i] == 0) {
        ans[q_id] = i;
        break;
      }
    }
  }
  end = std::chrono::steady_clock::now();
  cerr << "Point4"
       << std::chrono::duration_cast<std::chrono::microseconds>(end - begin)
              .count()
       << "\n";
  cerr << "op_count = " << op_count << endl;
  for (long long int i = 0; i < q; i++) {
    if (T[i] == 1) cout << ans[i] << "\n";
  }
  return 0;
}