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;
template <size_t BUF_LEN>
struct FastIn {
  char nxt_ch() {
    static char buf[BUF_LEN], *pst = buf + BUF_LEN, *ped = buf + BUF_LEN;
    if (pst == ped) {
      pst = buf;
      ped = buf + fread(buf, 1, BUF_LEN, stdin);
      if (pst == ped) return 0;
    }
    return *pst++;
  }
  int read_int() {
    char c;
    while ((c = nxt_ch()) < 48)
      ;
    int x = c - 48;
    for (; 47 < (c = nxt_ch()); x = x * 10 + c - 48)
      ;
    return x;
  }
};
template <typename D>
struct MapZ {
  vector<D> dat;
  map<D, int> mp;
  MapZ(const vector<D> &d) : dat(d) {
    sort(dat.begin(), dat.end());
    dat.erase(unique(dat.begin(), dat.end()), dat.end());
    for (int i = 0; i < dat.size(); ++i) mp[dat[i]] = i;
  }
  int operator()(const D &x) { return mp[x]; }
  int operator[](int x) { return dat[x]; }
};
signed main() {
  FastIn<1 << 15> fin;
  int N = fin.read_int();
  int Q = fin.read_int();
  vector<int> A(N);
  for (int i = 0; i < N; ++i) A[i] = fin.read_int();
  vector<tuple<int, int, int>> R(Q);
  for (int i = 0; i < Q; ++i) {
    int a = fin.read_int();
    int b = fin.read_int();
    int c = fin.read_int();
    R[i] = make_tuple(a, b - 1, c);
  }
  vector<int> vals;
  for (int i = 0; i < N; ++i) vals.push_back(A[i]);
  for (int i = 0; i < Q; ++i) vals.push_back(get<2>(R[i]));
  MapZ<int> mp_vals(vals);
  for (int i = 0; i < N; ++i) A[i] = mp_vals(A[i]);
  for (int i = 0; i < Q; ++i)
    if (get<0>(R[i]) == 2) get<2>(R[i]) = mp_vals(get<2>(R[i]));
  const int BS = 2000;
  vector<tuple<int, int, int, int, int>> fq;
  vector<tuple<int, int>> mq;
  for (int i = 0, acc_t = 0; i < Q; ++i) {
    int a, b, c;
    tie(a, b, c) = R[i];
    if (a == 1) {
      fq.emplace_back(acc_t / BS, b / BS, c, i, acc_t);
    } else {
      ++acc_t;
      mq.emplace_back(b, c);
    }
  }
  sort(fq.begin(), fq.end());
  vector<int> ans(Q, -1);
  for (auto q : fq) {
    static int tb = 0, lb = 0, rb = 0;
    static int c[1 << 20];
    static int cc[1 << 20];
    int x = get<3>(q);
    int t = get<4>(q);
    int op, ql, qr;
    tie(op, ql, qr) = R[x];
    assert(op == 1);
    auto add = [&](int v, int s) {
      --cc[c[v]];
      c[v] += s;
      ++cc[c[v]];
    };
    while (tb < t) {
      int p, v;
      tie(p, v) = mq[tb];
      if (lb <= p && p < rb) {
        add(v, 1);
        add(A[p], -1);
      }
      swap(A[p], get<1>(mq[tb++]));
    }
    while (t < tb) {
      int p, v;
      tie(p, v) = mq[--tb];
      if (lb <= p && p < rb) {
        add(v, 1);
        add(A[p], -1);
      }
      swap(A[p], get<1>(mq[tb]));
    }
    while (ql < lb) add(A[--lb], 1);
    while (rb < qr) add(A[rb++], 1);
    while (qr < rb) add(A[--rb], -1);
    while (lb < ql) add(A[lb++], -1);
    for (ans[x] = 1; cc[ans[x]]; ++ans[x])
      ;
  }
  for (int i = 0; i < Q; ++i)
    if (~ans[i]) printf("%d\n", ans[i]);
  return 0;
}