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 <typename... As>
struct tpl : public std::tuple<As...> {
  using std::tuple<As...>::tuple;
  tpl() {}
  tpl(std::tuple<As...> const& b) { std::tuple<As...>::operator=(b); }
  template <typename T = tuple<As...>>
  typename tuple_element<0, T>::type const& x() const {
    return get<0>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<0, T>::type& x() {
    return get<0>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<1, T>::type const& y() const {
    return get<1>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<1, T>::type& y() {
    return get<1>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<2, T>::type const& z() const {
    return get<2>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<2, T>::type& z() {
    return get<2>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<3, T>::type const& w() const {
    return get<3>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<3, T>::type& w() {
    return get<3>(*this);
  }
};
using lli = int;
using llu = long long unsigned;
using pii = tpl<lli, lli>;
using piii = tpl<lli, lli, lli>;
using piiii = tpl<lli, lli, lli, lli>;
using vi = vector<lli>;
using vii = vector<pii>;
using viii = vector<piii>;
using vvi = vector<vi>;
using vvii = vector<vii>;
using vviii = vector<viii>;
template <class T>
using min_queue = priority_queue<T, vector<T>, greater<T>>;
template <class T>
using max_queue = priority_queue<T>;
template <size_t... I>
struct my_index_sequence {
  using type = my_index_sequence;
  static constexpr array<size_t, sizeof...(I)> value = {{I...}};
};
namespace my_index_sequence_detail {
template <typename I, typename J>
struct concat;
template <size_t... I, size_t... J>
struct concat<my_index_sequence<I...>, my_index_sequence<J...>>
    : my_index_sequence<I..., (sizeof...(I) + J)...> {};
template <size_t N>
struct make_index_sequence
    : concat<typename make_index_sequence<N / 2>::type,
             typename make_index_sequence<N - N / 2>::type>::type {};
template <>
struct make_index_sequence<0> : my_index_sequence<> {};
template <>
struct make_index_sequence<1> : my_index_sequence<0> {};
}  // namespace my_index_sequence_detail
template <class... A>
using my_index_sequence_for =
    typename my_index_sequence_detail::make_index_sequence<sizeof...(A)>::type;
template <class T, size_t... I>
void print_tuple(ostream& s, T const& a, my_index_sequence<I...>) {
  using swallow = int[];
  (void)swallow{0, (void(s << (I == 0 ? "" : ", ") << get<I>(a)), 0)...};
}
template <class T>
ostream& print_collection(ostream& s, T const& a);
template <class... A>
ostream& operator<<(ostream& s, tpl<A...> const& a);
template <class... A>
ostream& operator<<(ostream& s, tuple<A...> const& a);
template <class A, class B>
ostream& operator<<(ostream& s, pair<A, B> const& a);
template <class T, size_t I>
ostream& operator<<(ostream& s, array<T, I> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, vector<T> const& a) {
  return print_collection(s, a);
}
template <class T, class U>
ostream& operator<<(ostream& s, multimap<T, U> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, multiset<T> const& a) {
  return print_collection(s, a);
}
template <class T, class U>
ostream& operator<<(ostream& s, map<T, U> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, set<T> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& print_collection(ostream& s, T const& a) {
  s << '[';
  for (auto it = begin(a); it != end(a); ++it) {
    s << *it;
    if (it != prev(end(a))) s << " ";
  }
  return s << ']';
}
template <class... A>
ostream& operator<<(ostream& s, tpl<A...> const& a) {
  s << '(';
  print_tuple(s, a, my_index_sequence_for<A...>{});
  return s << ')';
}
template <class... A>
ostream& operator<<(ostream& s, tuple<A...> const& a) {
  s << '(';
  print_tuple(s, a, my_index_sequence_for<A...>{});
  return s << ')';
}
template <class A, class B>
ostream& operator<<(ostream& s, pair<A, B> const& a) {
  return s << "(" << get<0>(a) << ", " << get<1>(a) << ")";
}
const int BSZ = 4000;
const int N = 1e5;
int at[N];
int from[N], to[N];
bool cmp(tpl<int, int, int> const& a, tpl<int, int, int> const& b) {
  bool sw1 = ((a.x() / BSZ) & 1) ? -1 : 1;
  bool sw2 = (((a.x() / BSZ) & 1) ^ ((a.y() / BSZ) & 1)) ? -1 : 1;
  return make_tuple(a.x() / BSZ, sw1 * a.y() / BSZ, sw2 * a.z()) <
         make_tuple(b.x() / BSZ, sw1 * b.y() / BSZ, sw2 * b.z());
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  vi A(n);
  for (lli i = 0; i < (lli)(n); ++i) cin >> A[i];
  auto B = A;
  vector<tpl<int, int, int>> QS;
  map<int, int> MM;
  auto getM = [&](int x) {
    if (MM.count(x)) return MM[x];
    int y = MM.size();
    MM[x] = y;
    return y;
  };
  int time = 0;
  for (lli i = 0; i < (lli)(q); ++i) {
    int ty;
    cin >> ty;
    if (ty == 1) {
      lli l, r;
      cin >> l >> r;
      --l;
      --r;
      QS.push_back(make_tuple(l, r, time));
    } else {
      lli j, x;
      cin >> j >> x;
      --j;
      at[time] = j;
      to[time] = getM(x);
      from[time] = getM(B[j]);
      B[j] = x;
      time += 1;
    }
  }
  q = QS.size();
  for (lli i = 0; i < (lli)(n); ++i) A[i] = getM(A[i]);
  vi I(q);
  iota(begin(I), end(I), 0);
  sort(begin(I), end(I), [&](int i, int j) { return cmp(QS[i], QS[j]); });
  vi SZ(MM.size());
  vi R(n + 10);
  auto rem = [&](int x) {
    int y = SZ[x]--;
    if (y < 1) exit(0);
    R[y]--;
    R[y - 1]++;
  };
  auto add = [&](int x) {
    int y = SZ[x]++;
    if (y < 0) exit(0);
    R[y + 1]++;
    R[y]--;
  };
  int cl = 0, cr = -1, ct = 0;
  vi ans(q);
  for (int i : I) {
    int l, r, t;
    tie(l, r, t) = QS[i];
    while (ct < t) {
      if (cl <= at[ct] && at[ct] <= cr) {
        rem(from[ct]);
        add(to[ct]);
      }
      A[at[ct]] = to[ct];
      ct++;
    }
    while (ct > t) {
      --ct;
      if (cl <= at[ct] && at[ct] <= cr) {
        rem(to[ct]);
        add(from[ct]);
      }
      A[at[ct]] = from[ct];
    }
    while (cr < r) {
      cr++;
      add(A[cr]);
    }
    while (cl > l) {
      cl--;
      add(A[cl]);
    }
    while (cr > r) {
      rem(A[cr]);
      --cr;
    }
    while (cl < l) {
      rem(A[cl]);
      ++cl;
    }
    ans[i] = 1;
    while (R[ans[i]]) ans[i]++;
  }
  for (lli i = 0; i < (lli)(q); ++i) cout << ans[i] << '\n';
  cout << flush;
  return 0;
}