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;
struct Query {
  int id, left, right, time, blockLeft, blockRight;
  Query()
      : id(-1), left(-1), right(-1), time(-1), blockLeft(-1), blockRight(-1) {}
  Query(int id, int left, int right, int time, int blockLeft, int blockRight)
      : id(id),
        left(left),
        right(right),
        time(time),
        blockLeft(blockLeft),
        blockRight(blockRight) {}
  bool operator<(const Query &otherQuery) const {
    if (blockLeft != otherQuery.blockLeft) {
      return blockLeft < otherQuery.blockLeft;
    }
    if (blockRight != otherQuery.blockRight) {
      return blockRight < otherQuery.blockRight;
    }
    return time < otherQuery.time;
  }
};
struct Operation {
  int pos, oldValue, newValue;
  Operation() : pos(-1), oldValue(-1), newValue(-1) {}
  Operation(int pos, int oldValue, int newValue)
      : pos(pos), oldValue(oldValue), newValue(newValue) {}
};
void del(int value, int *cnts, int *saveValues) {
  saveValues[cnts[value]]--;
  cnts[value]--;
  saveValues[cnts[value]]++;
}
void add(int value, int *cnts, int *saveValues) {
  saveValues[cnts[value]]--;
  cnts[value]++;
  saveValues[cnts[value]]++;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, q;
  cin >> n >> q;
  int sqrtValue = pow(n, 2.0 / 3.0), *values = new int[n + 1],
      *tmpValues = new int[n + 1];
  if (sqrtValue == 0) sqrtValue = 1;
  vector<int> disValues;
  for (int i = 1; i <= n; i++) {
    cin >> values[i];
    tmpValues[i] = values[i];
    disValues.push_back(values[i]);
  }
  Query *querys = new Query[q + 1];
  Operation *opts = new Operation[q + 1];
  int cntQuerys = 0, cntOpts = 0;
  for (int i = 1; i <= q; i++) {
    int opt;
    cin >> opt;
    if (opt == 1) {
      int left, right;
      cin >> left >> right;
      ++cntQuerys;
      querys[cntQuerys] = Query(cntQuerys, left, right, cntOpts,
                                left / sqrtValue, right / sqrtValue);
    } else {
      int pos, value;
      cin >> pos >> value;
      ++cntOpts;
      opts[cntOpts] = Operation(pos, tmpValues[pos], value);
      tmpValues[pos] = value;
      disValues.push_back(value);
    }
  }
  sort(disValues.begin(), disValues.end());
  disValues.resize(unique(disValues.begin(), disValues.end()) -
                   disValues.begin());
  for (int i = 1; i <= cntOpts; i++) {
    Operation &tmpOpt = opts[i];
    tmpOpt.oldValue =
        lower_bound(disValues.begin(), disValues.end(), tmpOpt.oldValue) -
        disValues.begin();
    tmpOpt.newValue =
        lower_bound(disValues.begin(), disValues.end(), tmpOpt.newValue) -
        disValues.begin();
  }
  for (int i = 1; i <= n; i++) {
    values[i] = lower_bound(disValues.begin(), disValues.end(), values[i]) -
                disValues.begin();
  }
  int valueSize = static_cast<int>(disValues.size()),
      *cnts = new int[valueSize + 3], *saveValues = new int[n + 2];
  memset(cnts, 0, sizeof(int) * (valueSize + 3));
  memset(saveValues, 0, sizeof(int) * (n + 2));
  int *results = new int[cntQuerys + 1];
  sort(querys + 1, querys + cntQuerys + 1);
  int l = 1, r = 0, time = 0;
  for (int i = 1; i <= cntQuerys; i++) {
    Query &tmpQuery = querys[i];
    while (r < tmpQuery.right) {
      r++;
      add(values[r], cnts, saveValues);
    }
    while (l > tmpQuery.left) {
      l--;
      add(values[l], cnts, saveValues);
    }
    while (r > tmpQuery.right) {
      del(values[r], cnts, saveValues);
      r--;
    }
    while (l < tmpQuery.left) {
      del(values[l], cnts, saveValues);
      l++;
    }
    while (time < tmpQuery.time) {
      time++;
      Operation &tmpOpt = opts[time];
      if (tmpOpt.pos >= l && tmpOpt.pos <= r) {
        del(tmpOpt.oldValue, cnts, saveValues);
        add(tmpOpt.newValue, cnts, saveValues);
      }
      values[tmpOpt.pos] = tmpOpt.newValue;
    }
    while (time > tmpQuery.time) {
      Operation &tmpOpt = opts[time];
      if (tmpOpt.pos >= l && tmpOpt.pos <= r) {
        del(tmpOpt.newValue, cnts, saveValues);
        add(tmpOpt.oldValue, cnts, saveValues);
      }
      values[tmpOpt.pos] = tmpOpt.oldValue;
      time--;
    }
    for (int i = 1;; i++) {
      if (i > n) {
        results[tmpQuery.id] = 0;
      }
      if (saveValues[i] == 0) {
        results[tmpQuery.id] = i;
        break;
      }
    }
  }
  for (int i = 1; i <= cntQuerys; i++) {
    cout << results[i] << endl;
  }
  return 0;
}