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 = 2e5 + 5;
const int maxm = 5e2 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
int id[maxn];
struct Qr {
  int l, r, t, p;
  bool operator<(const Qr &o) const {
    return id[l] == id[o.l] ? (id[r] == id[o.r] ? t < o.t : id[r] < id[o.r])
                            : id[l] < id[o.l];
  }
} qr1[maxn], qr2[maxn];
int xi[maxn], tot;
int a[maxn], sum[maxn];
int ans[maxn], vis[maxn];
int c[maxn];
int n, m, m1, m2;
void update(int x, int val) {
  if (!x) return;
  if (val == 1) {
    ++vis[x];
    if (vis[x] >= 2) return;
  } else {
    --vis[x];
    if (vis[x]) return;
  }
  while (x <= 1000) c[x] += val, x += ((x) & (-x));
}
int query() {
  int ret = 0, sum = 0;
  for (int i = log(1000); ~i; --i) {
    ret += 1 << i, sum += c[ret];
    if (ret >= 1000 || sum != ret) sum -= c[ret], ret -= 1 << i;
  }
  return ret + 1;
}
void add(int x) {
  update(sum[x], -1);
  ++sum[x];
  update(sum[x], 1);
}
void del(int x) {
  update(sum[x], -1);
  --sum[x];
  update(sum[x], 1);
}
void modify(int l, int r, int p) {
  int pos = qr2[p].l, pre = a[pos], val = qr2[p].r;
  if (pos >= l && pos <= r) {
    update(sum[pre], -1), --sum[pre], update(sum[pre], 1);
    update(sum[val], -1), ++sum[val], update(sum[val], 1);
  }
  qr2[p].r = a[pos], a[pos] = val;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), xi[++tot] = a[i];
  int len = pow(n, 2.0 / 3);
  for (int i = 1; i <= n; ++i) id[i] = (i - 1) / len + 1;
  for (int i = 1; i <= m; ++i) {
    int opt, l, r;
    scanf("%d%d%d", &opt, &l, &r);
    if (opt == 1)
      qr1[++m1] = {l, r, i, m1};
    else
      qr2[++m2] = {l, r, i, m2}, xi[++tot] = r;
  }
  sort(xi + 1, xi + 1 + tot);
  tot = unique(xi + 1, xi + 1 + tot) - xi - 1;
  for (int i = 1; i <= n; ++i)
    a[i] = lower_bound(xi + 1, xi + 1 + tot, a[i]) - xi;
  for (int i = 1; i <= m2; ++i)
    qr2[i].r = lower_bound(xi + 1, xi + 1 + tot, qr2[i].r) - xi;
  sort(qr1 + 1, qr1 + 1 + m1);
  int l = 1, r = 0, p = 0;
  for (int i = 1; i <= m1; ++i) {
    while (l > qr1[i].l) --l, add(a[l]);
    while (r < qr1[i].r) ++r, add(a[r]);
    while (l < qr1[i].l) del(a[l]), ++l;
    while (r > qr1[i].r) del(a[r]), --r;
    while (p < m2 && qr2[p + 1].t < qr1[i].t) ++p, modify(l, r, p);
    while (p && qr2[p].t > qr1[i].t) modify(l, r, p), --p;
    int ret = 1;
    while (vis[ret]) ++ret;
    ans[qr1[i].p] = ret;
  }
  for (int i = 1; i <= m1; ++i) printf("%d\n", ans[i]);
  return 0;
}