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;
const int Maxn = 1e5 + 5;
const int d = 4000;
class que {
 public:
  int l, r, x, id;
  bool operator<(const que &o) const {
    return (l / d < o.l / d) ||
           (l / d == o.l / d &&
            (r / d < o.r / d || (r / d == o.r / d && x < o.x)));
  }
};
class mod {
 public:
  int pos, val;
};
que q[Maxn];
mod m[Maxn], rm[Maxn];
int n, qs;
int Q = 0, M = 0;
int t, b, c;
int a[Maxn];
int l = 1, r = 1, x = 0;
set<int> ss;
unordered_map<int, int> mp;
int cnt[Maxn << 1], sz[Maxn];
int ans[Maxn];
void add(int p) {
  sz[cnt[a[p]]]--;
  cnt[a[p]]++;
  sz[cnt[a[p]]]++;
}
void del(int p) {
  sz[cnt[a[p]]]--;
  cnt[a[p]]--;
  sz[cnt[a[p]]]++;
}
void xadd(int p) {
  if (l <= m[p].pos && m[p].pos <= r) {
    sz[cnt[a[m[p].pos]]]--;
    cnt[a[m[p].pos]]--;
    sz[cnt[a[m[p].pos]]]++;
    sz[cnt[m[p].val]]--;
    cnt[m[p].val]++;
    sz[cnt[m[p].val]]++;
  }
  a[m[p].pos] = m[p].val;
}
void xdel(int p) {
  if (l <= rm[p].pos && rm[p].pos <= r) {
    sz[cnt[a[rm[p].pos]]]--;
    cnt[a[rm[p].pos]]--;
    sz[cnt[a[rm[p].pos]]]++;
    sz[cnt[rm[p].val]]--;
    cnt[rm[p].val]++;
    sz[cnt[rm[p].val]]++;
  }
  a[rm[p].pos] = rm[p].val;
}
int calc() {
  int rez = 1;
  while (sz[rez]) rez++;
  return rez;
}
int main() {
  scanf("%d%d", &n, &qs);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  for (int i = 1; i <= qs; i++) {
    scanf("%d%d%d", &t, &b, &c);
    if (t == 1) {
      q[Q] = {b, c, M, Q};
      Q++;
    } else {
      m[M] = {b, c};
      M++;
    }
  }
  for (int i = 1; i <= n; i++) {
    if (!mp[a[i]]) {
      mp[a[i]] = 1;
      ss.insert(a[i]);
    }
  }
  for (int i = 0; i < M; i++) {
    if (!mp[m[i].val]) {
      mp[m[i].val] = 1;
      ss.insert(m[i].val);
    }
  }
  int rk = 1;
  for (auto v : ss) {
    mp[v] = rk++;
  }
  for (int i = 1; i <= n; i++) {
    a[i] = mp[a[i]];
  }
  for (int i = 0; i < M; i++) {
    m[i].val = mp[m[i].val];
  }
  for (int i = 0; i < M; i++) {
    rm[i].pos = m[i].pos;
    rm[i].val = a[m[i].pos];
    a[m[i].pos] = m[i].val;
  }
  for (int i = M - 1; i >= 0; i--) {
    a[rm[i].pos] = rm[i].val;
  }
  sort(q, q + Q);
  cnt[a[1]]++;
  sz[1]++;
  for (int i = 0; i < Q; i++) {
    while (x > q[i].x) xdel(--x);
    while (x < q[i].x) xadd(x++);
    while (l > q[i].l) add(--l);
    while (r < q[i].r) add(++r);
    while (l < q[i].l) del(l++);
    while (r > q[i].r) del(r--);
    ans[q[i].id] = calc();
  }
  for (int i = 0; i < Q; i++) printf("%d\n", ans[i]);
  return 0;
}