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 = 100005, maxm = 100005, maxw = 200005;
int base;
struct query {
  int id;
  int x, y, t;
  bool operator<(query i) const {
    return x / base == i.x / base ? (y / base == i.y / base ? t < i.t : y < i.y)
                                  : x < i.x;
  }
} q[maxm];
struct node {
  int id, s;
  bool operator<(node i) const { return s < i.s; }
} b[maxn + maxm];
int c[maxn];
int a[maxm][2];
int l, r, p;
int ans = 0;
int ANS[maxm];
int cnt[maxw];
int st[maxn];
bool vis[maxm];
inline int read() {
  register int x = 0, y = 1;
  register char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') y = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
  return x * y;
}
inline void write(register int x) {
  if (!x) return;
  write(x / 10);
  putchar(x % 10 + '0');
  return;
}
inline void ins(register int x) {
  st[cnt[c[x]]]--;
  cnt[c[x]]++;
  st[cnt[c[x]]]++;
  return;
}
inline void del(register int x) {
  st[cnt[c[x]]]--;
  cnt[c[x]]--;
  st[cnt[c[x]]]++;
  return;
}
inline void change(register int x) {
  if (a[x][0] >= l && a[x][0] <= r) del(a[x][0]);
  swap(c[a[x][0]], a[x][1]);
  if (a[x][0] >= l && a[x][0] <= r) ins(a[x][0]);
  return;
}
int main() {
  register int n, m;
  n = read();
  m = read();
  base = pow(n, 0.66666);
  for (register int i = 1; i <= n; i++) {
    b[i].id = i;
    b[i].s = read();
  }
  register int tot = 0, tim = 0;
  for (register int i = 1; i <= m; i++) {
    register int opt, x, y;
    opt = read();
    x = read();
    y = read();
    if (opt == 1) {
      tot++;
      vis[i] = 1;
      q[tot].id = i;
      q[tot].x = x;
      q[tot].y = y;
      q[tot].t = tim;
    } else {
      tim++;
      a[tim][0] = x;
      b[tim + n].id = tim + n;
      b[tim + n].s = y;
    }
  }
  sort(b + 1, b + n + tim + 1);
  int w = 0;
  for (int i = 1; i <= n + tim; i++) {
    if (b[i].s > b[i - 1].s) w++;
    if (b[i].id <= n)
      c[b[i].id] = w;
    else
      a[b[i].id - n][1] = w;
  }
  sort(q + 1, q + tot + 1);
  l = 1;
  r = 0;
  p = 0;
  for (register int i = 1; i <= tot; i++) {
    int x = q[i].x, y = q[i].y, t = q[i].t;
    while (l < x) del(l++);
    while (l > x) ins(--l);
    while (r < y) ins(++r);
    while (r > y) del(r--);
    while (p < t) change(++p);
    while (p > t) change(p--);
    ans = 0;
    while (st[ans + 1]) ans++;
    ANS[q[i].id] = ans + 1;
  }
  for (register int i = 1; i <= m; i++) {
    if (!vis[i]) continue;
    write(ANS[i]);
    if (!ANS[i]) putchar('0');
    putchar('\n');
  }
  return 0;
}