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 inf = 1e9;
const int maxn = 2e5 + 10;
struct Query2 {
  int p, x;
} q2[maxn];
struct Query1 {
  int l, r, t, pos;
} q1[maxn];
int n, m, B, tot, tot1, tot2, mn = inf, top, a[maxn], cnt[maxn], f[maxn],
                              ans[maxn], lst[maxn], sta[maxn];
int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
void print(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) print(x / 10);
  putchar(x % 10 + '0');
}
void write(int x) {
  print(x);
  puts("");
}
bool cmp(Query1 x, Query1 y) {
  return x.l / B == y.l / B
             ? (x.r / B == y.r / B ? x.t < y.t : x.r / B < y.r / B)
             : x.l / B < y.l / B;
}
void add(int x) {
  f[cnt[x]]--;
  cnt[x]++;
  f[cnt[x]]++;
}
void del(int x) {
  f[cnt[x]]--;
  cnt[x]--;
  f[cnt[x]]++;
}
void change(int x, int tim) {
  if (q1[x].l <= q2[tim].p && q2[tim].p <= q1[x].r) {
    del(a[q2[tim].p]);
    add(q2[tim].x);
  }
  swap(a[q2[tim].p], q2[tim].x);
}
int main() {
  n = read();
  m = read();
  B = pow(n, 0.666666);
  for (int i = 1; i <= n; i++) a[i] = read(), lst[++tot] = a[i];
  for (int i = 1; i <= m; i++) {
    int opt = read(), x = read(), y = read();
    if (opt == 1)
      q1[++tot1] = (Query1){x, y, tot2, tot1};
    else
      q2[++tot2] = (Query2){x, y}, lst[++tot] = q2[tot2].x;
  }
  sort(q1 + 1, q1 + tot1 + 1, cmp);
  int l = 1, r = 0, now = 0;
  sta[++top] = mn;
  sort(lst + 1, lst + tot + 1);
  tot = unique(lst + 1, lst + tot + 1) - lst - 1;
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(lst + 1, lst + tot + 1, a[i]) - lst;
  for (int i = 1; i <= tot2; i++)
    q2[i].x = lower_bound(lst + 1, lst + tot + 1, q2[i].x) - lst;
  for (int i = 1; i <= tot1; i++) {
    while (l > q1[i].l) add(a[--l]);
    while (r < q1[i].r) add(a[++r]);
    while (l < q1[i].l) del(a[l++]);
    while (r > q1[i].r) del(a[r--]);
    while (now < q1[i].t) change(i, ++now);
    while (now > q1[i].t) change(i, now--);
    for (int j = 1; j <= n; j++)
      if (!f[j]) {
        ans[q1[i].pos] = j;
        break;
      }
  }
  for (int i = 1; i <= tot1; i++) write(ans[i]);
  return 0;
}