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;
int fx[] = {1, -1, 0, 0};
int fy[] = {0, 0, 1, -1};
int id, n, q, block_size = 2200, ans;
int arr[100005], answer[100005], freq[100005], cnt[2 * 100005];
pair<int, int> update[100005];
pair<pair<int, int>, pair<int, int> > qry[100005];
map<int, int> mp;
bool mo_cmp(pair<pair<int, int>, pair<int, int> > x,
            pair<pair<int, int>, pair<int, int> > y) {
  if (x.first.first / block_size != y.first.first / block_size)
    return x.first.first / block_size < y.first.first / block_size;
  if (x.first.second / block_size != y.first.second / block_size)
    return x.first.second / block_size < y.first.second / block_size;
  return x.second.first < y.second.first;
}
void add(int x) {
  freq[cnt[x]]--;
  cnt[x]++;
  freq[cnt[x]]++;
}
void Remove(int x) {
  freq[cnt[x]]--;
  cnt[x]--;
  freq[cnt[x]]++;
}
void _update(int i, int u, int v) {
  int idx = update[i].first;
  int val = update[i].second;
  if (idx > v or idx < u)
    swap(arr[idx], update[i].second);
  else {
    Remove(arr[idx]);
    add(val);
    swap(arr[idx], update[i].second);
  }
}
int main() {
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> arr[i];
    if (mp[arr[i]] == 0) {
      mp[arr[i]] = ++id;
      arr[i] = id;
    } else
      arr[i] = mp[arr[i]];
  }
  int up = 0, qr = 0;
  for (int i = 0; i < q; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    if (u == 1) {
      qry[qr] = make_pair(pair<int, int>(v, w), pair<int, int>(up, qr));
      qr++;
    } else {
      if (mp[w] == 0) mp[w] = ++id;
      update[++up] = pair<int, int>(v, mp[w]);
    }
  }
  sort(qry, qry + qr, mo_cmp);
  int ml = 1, mr = 0, mu = 0;
  for (int i = 0; i < qr; i++) {
    int l = qry[i].first.first;
    int r = qry[i].first.second;
    int u = qry[i].second.first;
    while (mu < u) {
      mu++;
      _update(mu, ml, mr);
    }
    while (mu > u) {
      _update(mu, ml, mr);
      mu--;
    }
    while (mr < r) {
      mr++;
      add(arr[mr]);
    }
    while (mr > r) {
      Remove(arr[mr]);
      mr--;
    }
    while (ml < l) {
      Remove(arr[ml]);
      ml++;
    }
    while (ml > l) {
      ml--;
      add(arr[ml]);
    }
    for (int j = 1; j <= 700; j++) {
      if (freq[j] == 0 and answer[qry[i].second.second] == 0) {
        answer[qry[i].second.second] = j;
        break;
      }
    }
  }
  for (int i = 0; i < qr; i++) cout << answer[i] << '\n';
  return 0;
}