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;
int read() {
  int res = 0, f = 1;
  char ch = ' ';
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    res = res * 10 + ch - '0';
    ch = getchar();
  }
  return res * f;
}
const int N = 2e5 + 5;
int n, m;
int a[N], belong[N], ans[N];
int pre[N], pos[N], num, c[N], sum1, sum2, _size, kkk, times, tot[N];
void write(int x) {
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
struct node1 {
  int l, r, id, pre;
} t[N];
struct node2 {
  int pos, color;
} p[N];
int cnt[N];
void del(int x) {
  tot[cnt[x]]--;
  tot[--cnt[x]]++;
}
void add(int x) {
  tot[cnt[x]]--;
  tot[++cnt[x]]++;
}
void work(int now, int i) {
  if (t[i].l <= p[now].pos && p[now].pos <= t[i].r) {
    del(a[p[now].pos]);
    add(p[now].color);
  }
  swap(p[now].color, a[p[now].pos]);
}
void solve() {
  int l = 1, r = 0, now = 0;
  for (register int i = 1; i <= sum1; i++) {
    int ql = t[i].l, qr = t[i].r;
    while (l < ql) del(a[l]), l++;
    while (l > ql) l--, add(a[l]);
    while (r < qr) r++, add(a[r]);
    while (r > qr) del(a[r]), r--;
    while (now < t[i].pre) work(++now, i);
    while (now > t[i].pre) work(now--, i);
    ans[t[i].id] = 1;
    while (tot[ans[t[i].id]]) {
      ans[t[i].id]++;
    }
  }
  for (register int i = 1; i <= sum1; i++) {
    write(ans[i]);
    puts("");
  }
}
bool cmp(node1 x, node1 y) {
  return belong[x.l] == belong[y.l]
             ? (belong[x.r] == belong[y.r] ? x.pre < y.pre : x.r < y.r)
             : x.l < y.l;
}
int main() {
  n = read();
  m = read();
  _size = pow(n, 0.66666666);
  kkk = ceil((double)n / _size);
  for (register int i = 1; i <= kkk; i++) {
    for (register int j = (i - 1) * _size + 1; j <= i * _size; j++) {
      belong[j] = i;
    }
  }
  for (register int i = 1; i <= n; i++) a[i] = read(), c[++num] = a[i];
  for (register int i = 1; i <= m; i++) {
    int opt = read(), x = read(), y = read();
    if (opt == 2) {
      c[++num] = y;
      sum2++;
      p[sum2].pos = x;
      p[sum2].color = y;
    }
    if (opt == 1) {
      sum1++;
      t[sum1].l = x;
      t[sum1].r = y;
      t[sum1].pre = sum2;
      t[sum1].id = sum1;
    }
  }
  sort(t + 1, t + 1 + sum1, cmp);
  sort(c + 1, c + 1 + num);
  times = unique(c + 1, c + 1 + num) - c - 1;
  for (register int i = 1; i <= n; i++) {
    a[i] = lower_bound(c + 1, c + 1 + num, a[i]) - c;
  }
  for (register int i = 1; i <= sum2; i++) {
    p[i].color = lower_bound(c + 1, c + 1 + num, p[i].color) - c;
  }
  solve();
  return 0;
}