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 = 1e6 + 5;
int n, m, k, u, L = 1, R = 0, t = 0, qq;
int cnt[N], dp[N], a[N], b[N];
pair<int, int> f[N];
pair<pair<int, int>, pair<int, int> > q[N];
int ans[N];
unordered_map<int, int> mp;
bool cmp(pair<pair<int, int>, pair<int, int> > a,
         pair<pair<int, int>, pair<int, int> > b) {
  if (a.first.first / k != b.first.first / k)
    return a.first.first / k < b.first.first / k;
  if (a.second.first / k != b.second.first / k)
    return a.second.first / k < b.second.first / k;
  return a.second.second < b.second.second;
}
void MO(int i) {
  while (R < q[i].second.second) {
    R++;
    cnt[dp[a[R]]++]--;
    cnt[dp[a[R]]]++;
  }
  while (R > q[i].second.second) {
    cnt[dp[a[R]]--]--;
    cnt[dp[a[R]]]++;
    R--;
  }
  while (L > q[i].second.first) {
    L--;
    cnt[dp[a[L]]++]--;
    cnt[dp[a[L]]]++;
  }
  while (L < q[i].second.first) {
    cnt[dp[a[L]]--]--;
    cnt[dp[a[L]]]++;
    L++;
  }
  while (t < q[i].first.first) {
    t++;
    if (L <= f[t].first && f[t].first <= R) {
      cnt[dp[a[f[t].first]]--]--;
      cnt[dp[a[f[t].first]]]++;
      cnt[dp[f[t].second]++]--;
      cnt[dp[f[t].second]]++;
    }
    swap(a[f[t].first], f[t].second);
  }
  while (t > q[i].first.first) {
    if (L <= f[t].first && f[t].first <= R) {
      cnt[dp[a[f[t].first]]--]--;
      cnt[dp[a[f[t].first]]]++;
      cnt[dp[f[t].second]++]--;
      cnt[dp[f[t].second]]++;
    }
    swap(a[f[t].first], f[t].second);
    t--;
  }
}
void sp(int &num) {
  register int c;
  num = 0;
  for (c = getchar(); c < 48 || c > 57; c = getchar())
    ;
  for (; c >= 48 && c <= 57; c = getchar()) num = num * 10 + c - 48;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  sp(n);
  sp(qq);
  for (int i = 1; i <= n; ++i) {
    sp(a[i]);
    b[i] = a[i];
  }
  int r = 0;
  for (int i = 1; i <= qq; ++i) {
    int type, x, y;
    sp(type);
    sp(x);
    sp(y);
    if (type == 2) {
      f[++r] = pair<int, int>(x, y);
      b[n + r] = y;
    } else {
      q[++u].second.first = x;
      q[u].second.second = y;
      q[u].first.first = r;
      q[u].first.second = i;
    }
  }
  int m = n + r;
  int rr = 0;
  sort(b + 1, b + 1 + m);
  b[0] = -1e9 + 7;
  for (int i = 1; i <= m; ++i) {
    if (b[i] != b[i - 1]) mp[b[i]] = ++rr;
  }
  for (int i = 1; i <= n; ++i) a[i] = mp[a[i]];
  for (int i = 1; i <= r; ++i) f[i].second = mp[f[i].second];
  mp.clear();
  k = pow(n, (double)2 / 3);
  sort(q + 1, q + 1 + u, cmp);
  for (int i = 1; i <= u; ++i) {
    MO(i);
    for (int j = 1; j <= 1e9 + 7; ++j)
      if (cnt[j] == 0) {
        ans[q[i].first.second] = j;
        break;
      }
  }
  for (int i = 1; i <= qq; ++i)
    if (ans[i] != 0) cout << ans[i] << "\n";
}