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 + 1;
inline int read() {
  char c;
  int out = 0;
  for (c = getchar(); c < '0' || c > '9'; c = getchar())
    ;
  for (; c >= '0' && c <= '9'; c = getchar()) {
    out = (out << 3) + (out << 1) + c - '0';
  }
  return out;
}
int tt[Maxn], num[Maxn];
int par[Maxn];
int n, m, tot;
int a[Maxn], b[Maxn];
struct Tri {
  int T, x, y, id;
  inline Tri(int T = 0, int x = 0, int y = 0, int id = 0)
      : T(T), x(x), y(y), id(id) {}
  inline bool operator<(const Tri &b) const {
    if (par[x] != par[b.x])
      return par[x] < par[b.x];
    else if (par[y] != par[b.y])
      return par[y] < par[b.y];
    else
      return T < b.T;
  }
} q[Maxn];
struct upd {
  int pos, pr, nx;
  inline upd(int pos = 0, int pr = 0, int nx = 0) : pos(pos), pr(pr), nx(nx) {}
};
upd update[Maxn];
inline void add(int x) {
  tt[num[x]]--;
  ++tt[++num[x]];
}
inline void del(int x) {
  tt[num[x]]--;
  ++tt[--num[x]];
}
int ans[Maxn];
int val[Maxn], ti;
int main() {
  n = read();
  m = read();
  tt[0] = Maxn;
  for (int i = 1; i <= n; ++i) {
    a[i] = read();
    b[i] = a[i];
    val[i] = a[i];
  }
  int tob = n;
  for (int i = 1; i <= m; ++i) {
    int x, y, z;
    x = read();
    y = read();
    z = read();
    if (x == 1)
      q[++tot] = Tri(ti, y, z, tot);
    else {
      b[++tob] = z;
      update[++ti] = upd(y, val[y], z);
      val[y] = z;
    }
  }
  sort(b + 1, b + tob + 1);
  int cntk = unique(b + 1, b + tob + 1) - b - 1;
  for (int i = 1; i <= n; ++i) {
    par[i] = i / 2153;
    a[i] = lower_bound(b + 1, b + cntk + 1, a[i]) - b;
  }
  for (int i = 1; i <= ti; ++i) {
    update[i].nx = lower_bound(b + 1, b + cntk + 1, update[i].nx) - b;
    update[i].pr = lower_bound(b + 1, b + cntk + 1, update[i].pr) - b;
  }
  sort(q + 1, q + tot + 1);
  int cur = 0, lc = 0, rc = 0;
  for (int i = 1; i <= tot; ++i) {
    int cx = q[i].x, cy = q[i].y, ct = q[i].T;
    while (cur < ct) {
      ++cur;
      int pp = update[cur].pos;
      if (lc <= pp && pp <= rc) del(a[pp]);
      a[pp] = update[cur].nx;
      if (lc <= pp && pp <= rc) add(a[pp]);
    }
    while (cur > ct) {
      int pp = update[cur].pos;
      if (lc <= pp && pp <= rc) del(a[pp]);
      a[pp] = update[cur].pr;
      if (lc <= pp && pp <= rc) add(a[pp]);
      --cur;
    }
    while (lc > cx) add(a[--lc]);
    while (rc < cy) add(a[++rc]);
    while (lc < cx) del(a[lc++]);
    while (rc > cy) del(a[rc--]);
    int cans;
    for (int j = 0; j < Maxn; ++j) {
      cans = j;
      if (tt[j] == 0) break;
    }
    ans[q[i].id] = cans;
  }
  for (int i = 1; i <= tot; ++i) printf("%d ", ans[i]);
  return 0;
}