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 = (int)1e9;
const int maxn = 100010;
const int maxbit = 18;
const int sz = 1500;
inline int read() {
  int x = 0, f = 1;
  char ch = 0;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
  return x * f;
}
struct node {
  int l, r, tid, ans, id;
  node() {}
  node(int _l, int _r, int _tid, int _ans, int _id) {
    l = _l;
    r = _r;
    tid = _tid;
    ans = _ans;
    id = _id;
  }
} que[maxn];
struct node2 {
  int p, fr, to;
  node2() {}
  node2(int _p, int _fr, int _to) {
    p = _p;
    fr = _fr;
    to = _to;
  }
} cz[maxn];
vector<int> oo;
inline int bl(int x) { return (x - 1) / sz; }
bool cmp(node x, node y) {
  if (bl(x.l) != bl(y.l))
    return x.l < y.l;
  else if (bl(x.r) != bl(y.r))
    return x.r < y.r;
  else
    return x.tid < y.tid;
}
bool cmp2(node x, node y) { return x.id < y.id; }
int n, q, cntz, cntq;
int a[maxn], fl[maxn], Now, L, R, cnt[maxn << 2];
inline void add(int x) {
  --fl[cnt[x]];
  ++fl[++cnt[x]];
}
inline void del(int x) {
  --fl[cnt[x]];
  ++fl[--cnt[x]];
}
inline void go(node2 &t) {
  if (t.p >= L && t.p <= R) del(t.fr), add(t.to);
  a[t.p] = t.to;
}
inline void re(node2 &t) {
  if (t.p >= L && t.p <= R) del(t.to), add(t.fr);
  a[t.p] = t.fr;
}
int main() {
  fl[0] = INF;
  n = read();
  q = read();
  for (int i = 1; i <= n; ++i) a[i] = read(), oo.push_back(a[i]);
  for (int i = 1; i <= q; ++i) {
    int t = read();
    if (t == 1) {
      int l = read(), r = read();
      que[++cntq] = node(l, r, Now, 0, i);
    } else {
      int p = read(), x = read();
      oo.push_back(x);
      cz[++cntz] = node2(p, a[p], x);
      a[p] = x;
      ++Now;
    }
  }
  sort(oo.begin(), oo.end());
  int ss = unique(oo.begin(), oo.end()) - oo.begin();
  oo.resize(ss);
  for (int i = 1; i <= n; ++i)
    a[i] = lower_bound(oo.begin(), oo.end(), a[i]) - oo.begin() + 1;
  for (int i = 1; i <= cntz; ++i) {
    cz[i].fr = lower_bound(oo.begin(), oo.end(), cz[i].fr) - oo.begin() + 1;
    cz[i].to = lower_bound(oo.begin(), oo.end(), cz[i].to) - oo.begin() + 1;
  }
  sort(que + 1, que + cntq + 1, cmp);
  for (int i = 1; i <= cntq; ++i) {
    node now = que[i];
    while (R < now.r) add(a[++R]);
    while (L > now.l) add(a[--L]);
    while (R > now.r) del(a[R--]);
    while (L < now.l) del(a[L++]);
    while (Now < now.tid) go(cz[++Now]);
    while (Now > now.tid) re(cz[Now--]);
    while (fl[que[i].ans]) ++que[i].ans;
  }
  sort(que + 1, que + cntq + 1, cmp2);
  for (int i = 1; i <= cntq; ++i) printf("%d\n", que[i].ans);
}