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;
inline int read() {
  int nm = 0, fh = 1;
  char cw = getchar();
  for (; !isdigit(cw); cw = getchar())
    if (cw == '-') fh = -1;
  for (; isdigit(cw); cw = getchar()) nm = nm * 10 + (cw - '0');
  return nm * fh;
}
int n, Q, K, a[200020], blg[200020], num[200020], len, T[200020], L, R, nowtms;
int top, tail, cnt[200020], ans[200020];
pair<int, int> sta[200020];
struct Query {
  int x, y, tms, id;
} que[200020];
inline bool cmp(Query a, Query b) {
  if (blg[a.x] ^ blg[b.x]) return blg[a.x] < blg[b.x];
  if (blg[a.y] ^ blg[b.y]) return blg[a.y] < blg[b.y];
  return a.tms < b.tms;
}
inline void ins(int x) {
  if (cnt[x]) --T[cnt[x]];
  cnt[x]++, T[cnt[x]]++;
}
inline void ers(int x) {
  --T[cnt[x]], --cnt[x];
  if (cnt[x]) T[cnt[x]]++;
}
inline void chg(int now) {
  int x = sta[now].first;
  if (L <= x && x <= R) ers(a[x]);
  swap(sta[now].second, a[x]);
  if (L <= x && x <= R) ins(a[x]);
}
inline int getmex() {
  for (int i = 1;; i++)
    if (!T[i]) return i;
}
int main() {
  n = read(), Q = read(), K = pow(n, 0.666666);
  for (int i = 1; i <= n; i++)
    a[i] = read(), num[++len] = a[i], blg[i] = (i - 1) / K + 1;
  for (int i = 1, op, x, y; i <= Q; i++) {
    op = read(), x = read(), y = read();
    if (op == 1)
      top++, que[top] = (Query){x, y, tail, top};
    else
      sta[++tail] = make_pair(x, y), num[++len] = y;
  }
  sort(num + 1, num + len + 1), len = unique(num + 1, num + len + 1) - num - 1;
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(num + 1, num + len + 1, a[i]) - num;
  for (int i = 1; i <= tail; i++)
    sta[i].second = lower_bound(num + 1, num + len + 1, sta[i].second) - num;
  sort(que + 1, que + top + 1, cmp);
  L = 1, R = nowtms = 0;
  for (int i = 1; i <= top; i++) {
    while (L > que[i].x) ins(a[--L]);
    while (R < que[i].y) ins(a[++R]);
    while (L < que[i].x) ers(a[L++]);
    while (R > que[i].y) ers(a[R--]);
    while (nowtms < que[i].tms) chg(++nowtms);
    while (nowtms > que[i].tms) chg(nowtms--);
    ans[que[i].id] = getmex();
  }
  for (int i = 1; i <= top; i++) printf("%d\n", ans[i]);
  return 0;
}