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 N = 1e5 + 10;
int n, q, v[N], vcnt, qa, qm, md[N][3], blo, ans[N];
int c[N << 1], num[N];
map<int, int> mp;
struct Query {
  int x, y, t, id;
  Query(int x = 0, int y = 0, int t = 0, int id = 0)
      : x(x), y(y), t(t), id(id) {}
} qu[N];
inline int Getid(int x) {
  if (mp[x]) return mp[x];
  return mp[x] = ++vcnt;
}
inline bool QCmp(Query u, Query v) {
  if (u.x / blo != v.x / blo) return u.x / blo < v.x / blo;
  if (u.y / blo != v.y / blo) return u.y / blo < v.y / blo;
  return u.t < v.t;
}
inline void Push(int x) {
  --num[c[x]];
  ++c[x];
  ++num[c[x]];
}
inline void Pop(int x) {
  --num[c[x]];
  --c[x];
  ++num[c[x]];
}
inline int Calc() {
  for (int i = 1; i <= n; ++i)
    if (!num[i]) return i;
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; ++i) scanf("%d", v + i), v[i] = Getid(v[i]);
  for (int i = 1, ty, x, y; i <= q; ++i) {
    scanf("%d%d%d", &ty, &x, &y);
    if (ty == 1)
      ++qa, qu[qa] = Query(x, y, qm, qa);
    else
      ++qm, md[qm][0] = x, md[qm][1] = v[x], md[qm][2] = Getid(y),
            v[x] = md[qm][2];
  }
  blo = pow(1ll * n * max(qm, 1), 1.0 / 3);
  sort(qu + 1, qu + qa + 1, QCmp);
  num[0] = vcnt;
  int l = 1, r = 0, t = qm;
  for (int i = 1; i <= qa; ++i) {
    while (r < qu[i].y) Push(v[++r]);
    while (l > qu[i].x) Push(v[--l]);
    while (l < qu[i].x) Pop(v[l++]);
    while (r > qu[i].y) Pop(v[r--]);
    while (t > qu[i].t) {
      v[md[t][0]] = md[t][1];
      if (l <= md[t][0] && md[t][0] <= r) Push(md[t][1]), Pop(md[t][2]);
      --t;
    }
    while (t < qu[i].t) {
      ++t;
      v[md[t][0]] = md[t][2];
      if (l <= md[t][0] && md[t][0] <= r) Push(md[t][2]), Pop(md[t][1]);
    }
    ans[qu[i].id] = Calc();
  }
  for (int i = 1; i <= qa; ++i) printf("%d\n", ans[i]);
  return 0;
}