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>
#pragma GCC optimize("Ofast")
const int mod = 1000000007;
const int inf = 1000000009;
const long long INF = 1000000000000000009;
const long long big = 1000000000000000;
const long double eps = 0.000000000000000000001;
using namespace std;
int pier;
struct update {
  int x, a, b;
};
struct zap {
  int p, k, ile, nr;
};
int p = 0, k = 0, u = -1;
vector<update> W;
vector<zap> Z;
int T[100005], A[100005], R[100005];
map<int, int> M;
int I[300005], Mex[300005];
bool cmp(zap a, zap b) {
  if (a.p / pier != b.p / pier) return a.p / pier < b.p / pier;
  if (a.k / pier != b.k / pier) a.k / pier < b.k / pier;
  return a.ile < b.ile;
}
bool cmp2(zap a, zap b) {
  if (a.p / pier != b.p / pier) return a.p / pier < b.p / pier;
  if (a.k / 100 != b.k / 100) return a.k / 100 < b.k / 100;
  return a.ile < b.ile;
}
void dodaj(int x) {
  Mex[I[x]]--;
  Mex[++I[x]]++;
}
void odejmij(int x) {
  Mex[I[x]]--;
  Mex[--I[x]]++;
}
void update(int x) {
  if (p <= W[x].x && W[x].x <= k) {
    odejmij(T[W[x].x]);
    dodaj(W[x].b);
  }
  T[W[x].x] = W[x].b;
}
void unupdate(int x) {
  if (p <= W[x].x && W[x].x <= k) {
    odejmij(T[W[x].x]);
    dodaj(W[x].a);
  }
  T[W[x].x] = W[x].a;
}
vector<int> P;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= 5000; i++) {
    if ((long long int)i * i * i <= (long long int)n * n * 2) pier = i;
  }
  pier = max(pier, 1);
  for (int i = 1; i <= n; i++) {
    cin >> T[i];
    P.push_back(T[i]);
    A[i] = T[i];
  }
  int ile = 0;
  for (int i = 1; i <= q; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    if (a == 1)
      Z.push_back({b, c, ile - 1, i - ile});
    else {
      P.push_back(c);
      ile++;
      W.push_back({b, A[b], c});
      A[b] = c;
    }
  }
  sort(P.begin(), P.end());
  int numer = 0;
  for (int i = 0; i < P.size(); i++) {
    if (i == 0 || P[i] != P[i - 1]) {
      numer++;
      M[P[i]] = numer;
    }
  }
  for (int i = 1; i <= n; i++) T[i] = M[T[i]];
  for (int i = 0; i < W.size(); i++) {
    W[i].a = M[W[i].a];
    W[i].b = M[W[i].b];
  }
  if (ile >= 30000)
    sort(Z.begin(), Z.end(), cmp);
  else
    sort(Z.begin(), Z.end(), cmp2);
  for (int i = 0; i < Z.size(); i++) {
    while (u > Z[i].ile) unupdate(u--);
    while (u < Z[i].ile) update(++u);
    while (p > Z[i].p) dodaj(T[--p]);
    while (k < Z[i].k) dodaj(T[++k]);
    while (p < Z[i].p) odejmij(T[p++]);
    while (k > Z[i].k) odejmij(T[k--]);
    for (int j = 1; j <= 5000; j++) {
      if (!Mex[j]) {
        R[Z[i].nr] = j;
        break;
      }
    }
  }
  for (int i = 1; i <= q - ile; i++) cout << R[i] << "\n";
  return 0;
}