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 = 500001;
struct query {
  int l, r, k, id;
  query(int l_ = 0, int r_ = 0, int k_ = 0, int id_ = 0) {
    l = l_;
    r = r_;
    k = k_;
    id = id_;
  }
} q[MAXN];
struct change {
  int i, nxt;
  change(int i_ = 0, int nxt_ = 0) {
    i = i_;
    nxt = nxt_;
  }
} c[MAXN];
struct node {
  int key, id;
  node(int key_ = 0, int id_ = 0) {
    key = key_;
    id = id_;
  }
} a_[MAXN];
int n, K, q_, m, k, s, t, now, a[MAXN], vis[MAXN], re[MAXN], val[MAXN], o,
    x_[MAXN], y_[MAXN];
bool cmp(query x, query y) {
  if (x.l / K == y.l / K) {
    if (x.r / K == y.r / K) {
      return x.k < y.k;
    } else
      return x.r < y.r;
  } else
    return x.l < y.l;
}
bool cmp_a(node x, node y) { return x.key < y.key; }
void add(int x) {
  val[vis[a[x]]]--;
  vis[a[x]]++;
  val[vis[a[x]]]++;
}
void erase(int x) {
  val[vis[a[x]]]--;
  vis[a[x]]--;
  val[vis[a[x]]]++;
}
void chang(int now) {
  if (s <= c[now].i && c[now].i <= t) erase(c[now].i);
  swap(a[c[now].i], c[now].nxt);
  if (s <= c[now].i && c[now].i <= t) add(c[now].i);
}
int main() {
  scanf("%d%d", &n, &q_);
  K = pow(n, (double)2 / double(3));
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a_[i] = node(a[i], i);
  for (int i = 1; i <= q_; i++) {
    scanf("%d", &o);
    if (o == 1) {
      int l, r;
      scanf("%d%d", &l, &r);
      m++;
      q[m] = query(l, r, k, m);
    } else {
      k++;
      scanf("%d%d", &x_[k], &y_[k]);
      a_[n + k] = node(y_[k], n + k);
    }
  }
  sort(a_ + 1, a_ + 1 + n + k, cmp_a);
  int cnt = 0;
  for (int i = 1; i <= n + k; i++) {
    if (a_[i].key != a_[i - 1].key) cnt++;
    if (a_[i].id <= n)
      a[a_[i].id] = cnt;
    else
      y_[a_[i].id - n] = cnt;
  }
  for (int i = 1; i <= k; i++) c[i] = change(x_[i], y_[i]);
  sort(q + 1, q + 1 + m, cmp);
  s = 1;
  t = 0;
  now = 0;
  for (int i_ = 1; i_ <= m; i_++) {
    int i = q[i_].id, l = q[i_].l, r = q[i_].r, ti = q[i_].k;
    while (s < l) erase(s++);
    while (s > l) add(--s);
    while (t < r) add(++t);
    while (t > r) erase(t--);
    while (now < ti) chang(++now);
    while (now > ti) chang(now--);
    int ans = 1;
    while (val[ans]) ans++;
    re[i] = ans;
  }
  for (int i = 1; i <= m; i++) printf("%d\n", re[i]);
}