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 <class T>
void _R(T &x) {
  cin >> x;
}
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &...tail) {
  _R(head);
  R(tail...);
}
template <class T>
void _W(const T &x) {
  cout << x;
}
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) {
  _W(x.first);
  putchar(' ');
  _W(x.second);
}
template <class T>
void _W(const vector<T> &x) {
  for (auto i = x.begin(); i != x.end(); _W(*i++))
    if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &...tail) {
  _W(head);
  putchar(sizeof...(tail) ? ' ' : '\n');
  W(tail...);
}
template <class T, class... U>
void DEBUG(const T &head, const U &...tail) {}
int MOD = 1e9 + 7;
void ADD(long long &x, long long v) {
  x = (x + v) % MOD;
  if (x < 0) x += MOD;
}
const int SIZE = 1e6 + 10;
int a[SIZE], b[SIZE], in[SIZE][3], ans[SIZE];
const int R_R = 1 << 11;
int cnt[SIZE], cul[SIZE];
int get_answer() {
  int ret = 1;
  while (cul[ret]) ret++;
  return ret;
}
void add(int y, int v) {
  cul[cnt[y]]--;
  cnt[y] += v;
  cul[cnt[y]]++;
}
void change(int x, int y) {
  if (x == y) return;
  add(b[x], -1);
  b[x] = y;
  add(b[x], 1);
}
int solve(int ll, int rr) {
  for (int i = (ll); i <= (rr); ++i) {
    add(b[i], 1);
  }
  int ret = get_answer();
  for (int i = (ll); i <= (rr); ++i) {
    add(b[i], -1);
  }
  return ret;
}
int main() {
  vector<int> d;
  memset((ans), -1, sizeof((ans)));
  int n, q;
  R(n, q);
  for (int i = 0; i < (n); ++i) {
    R(a[i]);
    d.push_back(a[i]);
  }
  for (int i = 0; i < (q); ++i) {
    for (int j = 0; j < (3); ++j) R(in[i][j]);
    if (in[i][0] == 1) {
      in[i][1]--;
      in[i][2]--;
    } else {
      in[i][1]--;
      d.push_back(in[i][2]);
    }
  }
  (sort(d.begin(), d.end()),
   d.resize(distance(d.begin(), unique(d.begin(), d.end()))));
  for (int i = 0; i < (n); ++i)
    b[i] = a[i] = (lower_bound(d.begin(), d.end(), a[i]) - d.begin());
  for (int i = 0; i < (q); ++i) {
    if (in[i][0] == 2) {
      in[i][2] = (lower_bound(d.begin(), d.end(), in[i][2]) - d.begin());
      b[in[i][1]] = in[i][2];
    } else {
      if (in[i][2] - in[i][1] <= R_R) ans[i] = solve(in[i][1], in[i][2]);
    }
  }
  for (int len = R_R; len < n; len += R_R) {
    for (int ll = 0; ll + len < n; ll += R_R) {
      int rr = ll + len + R_R;
      for (int i = (ll); i < (min(n, rr)); ++i) b[i] = a[i];
      for (int i = (ll + R_R); i < (ll + len); ++i) {
        add(b[i], 1);
      }
      for (int i = 0; i < (q); ++i) {
        if (in[i][0] == 2) {
          if (in[i][1] >= ll + R_R && in[i][1] < ll + len) {
            change(in[i][1], in[i][2]);
          } else {
            b[in[i][1]] = in[i][2];
          }
        } else {
          if (ans[i] == -1 && in[i][1] >= ll && in[i][2] < rr) {
            for (int j = (in[i][1]); j < (ll + R_R); ++j) {
              add(b[j], 1);
            }
            for (int j = (ll + len); j <= (in[i][2]); ++j) {
              add(b[j], 1);
            }
            ans[i] = get_answer();
            for (int j = (in[i][1]); j < (ll + R_R); ++j) {
              add(b[j], -1);
            }
            for (int j = (ll + len); j <= (in[i][2]); ++j) {
              add(b[j], -1);
            }
          }
        }
      }
      for (int i = (ll + R_R); i < (ll + len); ++i) {
        add(b[i], -1);
      }
    }
  }
  for (int i = 0; i < (q); ++i) {
    if (ans[i] != -1) W(ans[i]);
  }
  return 0;
}