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>
#pragma comment(linker, "/STACK:102400000,102400000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn], ans[maxn];
int p;
int sz[maxn], cnt[maxn];
struct CHANGE {
  int pos, v;
};
struct REQ {
  int l, r, id, nowchange;
};
vector<CHANGE> change;
vector<REQ> req;
map<int, int> hs;
bool cmp(REQ ta, REQ tb) {
  return ta.l / p == tb.l / p
             ? (ta.r / p == tb.r / p ? ta.nowchange < tb.nowchange
                                     : ta.r / p < tb.r / p)
             : ta.l < tb.l;
}
template <class T>
inline void scan_d(T &ret) {
  char c;
  ret = 0;
  while ((c = getchar()) < '0' || c > '9')
    ;
  while (c >= '0' && c <= '9') ret = ret * 10 + (c - '0'), c = getchar();
}
template <class T>
inline void print_d(T x) {
  if (x > 9) print_d(x / 10);
  putchar(x % 10 + '0');
}
void update(int pos, int mode) {
  --sz[cnt[pos]];
  cnt[pos] += mode;
  ++sz[cnt[pos]];
}
void chn(int now, int l, int r) {
  if (l <= change[now].pos && r >= change[now].pos)
    update(a[change[now].pos], -1);
  swap(a[change[now].pos], change[now].v);
  if (l <= change[now].pos && r >= change[now].pos)
    update(a[change[now].pos], 1);
}
int wls() {
  int t = 0;
  while (++t)
    if (sz[t] == 0) return t;
}
void gao() {
  int l = 1, r = 1, now = 0;
  update(a[1], 1);
  for (auto it : req) {
    for (; r < it.r; ++r) update(a[r + 1], 1);
    for (; r > it.r; --r) update(a[r], -1);
    for (; l < it.l; ++l) update(a[l], -1);
    for (; l > it.l; --l) update(a[l - 1], 1);
    for (; now < it.nowchange; ++now) chn(now, l, r);
    for (; now > it.nowchange; --now) chn(now - 1, l, r);
    ans[it.id] = wls();
  }
}
int main() {
  int i, j, k, m, n, q;
  scan_d(n);
  scan_d(q);
  for (int i = 1; i <= n; ++i) {
    scan_d(a[i]);
    a[i] = hs.count(a[i]) ? hs[a[i]] : (hs[a[i]] = hs.size() + 1);
  }
  int mode, ta, tb;
  p = pow(n, 2 / 3);
  p = 3000;
  for (int i = 1; i <= q; ++i) {
    scan_d(mode);
    scan_d(ta);
    scan_d(tb);
    if (mode == 1) {
      int tc = req.size(), td = change.size();
      req.emplace_back(REQ{ta, tb, tc, td});
    } else {
      tb = hs.count(tb) ? hs[tb] : (hs[tb] = hs.size() + 1);
      change.emplace_back(CHANGE{ta, tb});
    }
  }
  sort(req.begin(), req.end(), cmp);
  gao();
  for (int i = 0; i < req.size(); ++i) {
    print_d(ans[i]);
    putchar('\n');
  }
  return 0;
}