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 + 5, blk = 2150, sqrtn = 666;
struct node {
  int l, r, t, b1, b2, id;
  node() {}
  node(int L, int R, int T, int i) {
    l = L, r = R, t = T, id = i;
    b1 = l / blk, b2 = r / blk;
  }
  friend bool operator<(node a, node b) {
    if (a.b1 != b.b1) return a.b1 < b.b1;
    if (a.b2 != b.b2) return a.b2 < b.b2;
    return a.t < b.t;
  }
} p[maxn];
struct chnode {
  int x, y, pre;
  chnode() {}
  chnode(int X, int Y, int p) { x = X, y = Y, pre = p; }
} q[maxn];
int n, m, a[maxn], pre[maxn], l = 1, r, t, cnt[maxn], cc[maxn], qc, ac, cn,
                              sum[maxn], bc;
map<int, int> maps;
void revise(int x, bool v) {
  if (cnt[x] < sqrtn) cc[cnt[x]]--;
  v ? cnt[x]++ : cnt[x]--;
  if (cnt[x] < sqrtn) cc[cnt[x]]++;
}
void change(int x, int c) {
  if (x >= l && x <= r) revise(a[x], 0), revise(c, 1);
  a[x] = c;
}
void md(int i) {
  while (t < p[i].t) t++, change(q[t].x, q[t].y);
  while (t > p[i].t) change(q[t].x, q[t].pre), t--;
  while (l > p[i].l) revise(a[--l], 1);
  while (r < p[i].r) revise(a[++r], 1);
  while (l < p[i].l) revise(a[l++], 0);
  while (r > p[i].r) revise(a[r--], 0);
  for (register int j = 1; j <= sqrtn; j++) {
    if (!cc[j]) {
      sum[p[i].id] = j;
      break;
    }
  }
}
int main() {
  int op, x, y;
  scanf("%d%d", &n, &m);
  for (register int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    if (!maps[a[i]]) maps[a[i]] = ++bc;
    a[i] = maps[a[i]], pre[i] = a[i];
  }
  for (register int i = 1; i <= m; i++) {
    scanf("%d%d%d", &op, &x, &y);
    if (op == 1)
      qc++, p[qc] = node(x, y, ac, qc);
    else {
      if (!maps[y]) maps[y] = ++bc;
      y = maps[y], q[++ac] = chnode(x, y, pre[x]), pre[x] = y;
    }
  }
  sort(p + 1, p + qc + 1);
  for (register int i = 1; i <= qc; i++) md(i);
  for (register int i = 1; i <= qc; i++) printf("%d\n", sum[i]);
}