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;
struct opt {
  int t;
  int l;
  int r;
  int p;
  int id;
  int ans;
};
const int MAXN = 2e5 + 100;
int n, q, len;
int a[MAXN], cnt[MAXN], sz[2 * MAXN];
vector<int> b;
vector<opt> c, d;
void modify(int x, bool e) {
  --x;
  int l = a[d[x].l], r = d[x].r;
  if (e) {
    --sz[cnt[l]--];
    ++sz[cnt[l]];
    --sz[cnt[r]++];
    ++sz[cnt[r]];
  }
  swap(a[d[x].l], d[x].r);
}
void inc(int x) {
  --sz[cnt[a[x]]++];
  ++sz[cnt[a[x]]];
}
void dec(int x) {
  --sz[cnt[a[x]]--];
  ++sz[cnt[a[x]]];
}
int query() {
  int up = 2 * sqrt(n);
  for (int i = 1; i < up + 1; ++i) {
    if (sz[i + 100000] == 0) return i;
  }
}
int search(int x) {
  int l = 0, r = b.size() - 1;
  while (l < r) {
    int mid = (l + r + 1) / 2;
    if (b[mid] <= x)
      l = mid;
    else
      r = mid - 1;
  }
  return l;
}
bool cmp(const opt &x, const opt &y) {
  if (x.p / len != y.p / len)
    return x.p < y.p;
  else {
    if (x.l / len != y.l / len)
      return x.l < y.l;
    else
      return x.r < y.r;
  }
}
bool cmp2(const opt &x, const opt &y) { return x.id < y.id; }
int read() {
  int x;
  scanf("%d", &x);
  return x;
}
int main() {
  b.reserve(210000);
  n = read();
  q = read();
  for (int i = 1; i < n + 1; ++i) {
    a[i] = read();
    b.push_back(a[i]);
  }
  int o = 0;
  for (int i = 0; i < q; ++i) {
    opt t;
    t.t = read();
    t.l = read();
    t.r = read();
    t.p = d.size();
    t.id = i;
    if (t.t == 2) {
      b.push_back(t.r);
      d.push_back(t);
    } else
      c.push_back(t);
  }
  sort(b.begin(), b.end());
  auto it = unique(b.begin(), b.end());
  b.erase(it, b.end());
  for (int i = 1; i < n + 1; ++i) a[i] = search(a[i]);
  for (auto &i : d) i.r = search(i.r);
  for (int i = 0; i < b.size() + 1; ++i) cnt[i] = 100000;
  len = pow(n, 2.0 / 3.0);
  sort(c.begin(), c.end(), cmp);
  int l = 1, r = 0, h = 0;
  for (auto &i : c) {
    while (l > i.l) {
      --l;
      inc(l);
    }
    while (r < i.r) {
      ++r;
      inc(r);
    }
    while (l < i.l) {
      dec(l);
      ++l;
    }
    while (r > i.r) {
      dec(r);
      --r;
    }
    while (h < i.p) {
      ++h;
      modify(h, d[h - 1].l >= l && d[h - 1].l <= r);
    }
    while (h > i.p) {
      modify(h, d[h - 1].l >= l && d[h - 1].l <= r);
      --h;
    }
    i.ans = query();
  }
  sort(c.begin(), c.end(), cmp2);
  for (auto i : c) {
    printf("%d\n", i.ans);
  }
  return 0;
}