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;
namespace mine {
long long qread() {
  long long ans = 0, f = 1;
  char c = getchar();
  while (c < '0' or c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c and c <= '9') ans = ans * 10 + c - '0', c = getchar();
  return ans * f;
}
void write(long long num) {
  if (num < 0) putchar('-'), num = -num;
  if (num >= 10) write(num / 10);
  putchar('0' + num % 10);
}
void write1(long long num) {
  write(num);
  putchar(' ');
}
void write2(long long num) {
  write(num);
  putchar('\n');
}
template <typename T>
void chmax(T &x, const T y) {
  x = (x > y ? x : y);
}
template <typename T>
void chmin(T &x, const T y) {
  x = (x < y ? x : y);
}
long long gcd(long long x, long long y) { return y ? gcd(y, x % y) : x; }
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
inline int mm(const int x) { return x >= MOD ? x - MOD : x; }
template <typename T>
inline void add(T &x, const T y) {
  x = mm(x + y);
}
inline long long qpower(long long x, long long e) {
  long long ans = 1;
  if (e < 0) puts("error");
  while (e) {
    if (e & 1) ans = ans * x % MOD;
    x = x * x % MOD;
    e >>= 1;
  }
  return ans;
}
long long invm(long long x) { return qpower(x, MOD - 2); }
const int N = 1e6 + 10;
int ct[N];
int B = 2200;
int bk(int i) { return i / B; }
struct Qes {
  int l, r, tim, id;
} q[N];
int ans[N];
pair<int, int> ch[N];
bool cmp(Qes a, Qes b) {
  if (a.l / B != b.l / B) return a.l / B < b.l / B;
  if (a.r / B != b.r / B) return a.r / B < b.r / B;
  return a.tim < b.tim;
}
int a[N];
vector<int> ss;
int ct2[N], siz[N], BB = 320;
int fl = 1, fr = 0, tt = 0;
void add(int num, int op) {
  siz[ct[num] / BB]--, ct2[ct[num]]--;
  ct[num] += op;
  siz[ct[num] / BB]++, ct2[ct[num]]++;
}
void modify(int id) {
  if (fl <= ch[id].first and ch[id].first <= fr)
    add(a[ch[id].first], -1), add(ch[id].second, 1);
  swap(a[ch[id].first], ch[id].second);
}
void main() {
  int n = qread(), qq = qread();
  B = pow(n, 2.0 / 3);
  for (int i = 0; i < n; i++) a[i] = qread(), ss.push_back(a[i]);
  int cnt = 0;
  for (int i = 1; i <= qq; i++) {
    int op = qread();
    if (op == 1) {
      int l = qread() - 1, r = qread() - 1;
      q[i] = (Qes){l, r, cnt, i};
    } else {
      int pos = qread() - 1, num = qread();
      ch[++cnt] = make_pair(pos, num);
      ss.push_back(num);
    }
  }
  sort(q + 1, q + qq + 1, cmp);
  sort((ss).begin(), (ss).end());
  siz[0] = 1;
  for (int i = 0; i < n; i++)
    a[i] = lower_bound((ss).begin(), (ss).end(), a[i]) - ss.begin();
  for (int i = 1; i <= cnt; i++)
    ch[i].second =
        lower_bound((ss).begin(), (ss).end(), ch[i].second) - ss.begin();
  for (int i = 1; i <= qq; i++)
    if (q[i].id) {
      while (fl < q[i].l) add(a[fl++], -1);
      while (fl > q[i].l) add(a[--fl], 1);
      while (fr > q[i].r) add(a[fr--], -1);
      while (fr < q[i].r) add(a[++fr], 1);
      while (tt < q[i].tim) modify(++tt);
      while (tt > q[i].tim) modify(tt--);
      for (int j = 0; j <= BB; j++)
        if (siz[j] < BB) {
          for (int k = j * BB;; k++)
            if (!ct2[k]) {
              ans[q[i].id] = k;
              break;
            }
          break;
        }
    }
  for (int i = 1; i <= qq; i++)
    if (ans[i]) write2(ans[i]);
}
};  // namespace mine
int main() {
  srand(time(0));
  mine::main();
}