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 blk = 2000;
int n, q, a[100005], init[100005], qq, qu, ct[200005], pres[200005];
pair<pair<int, int>, int> upd[100005];
pair<pair<int, int>, pair<int, int> > qr[100005];
bool cmp(pair<pair<int, int>, pair<int, int> > p1,
         pair<pair<int, int>, pair<int, int> > p2) {
  if (p1.first.first / blk != p2.first.first / blk)
    return p1.first.first / blk < p2.first.first / blk;
  if (p1.first.second / blk != p2.first.second / blk)
    return p1.first.second / blk < p2.first.second / blk;
  return p1.second.first < p2.second.first;
}
int cl, cr, curtime;
void rmv(int ps) {
  if (ps == 0 || ps > n) return;
  int v = ps;
  pres[ct[a[v]]]--;
  ct[a[v]]--;
  pres[ct[a[v]]]++;
}
void add(int ps) {
  if (ps == 0 || ps > n) return;
  int v = ps;
  pres[ct[a[v]]]--;
  ct[a[v]]++;
  pres[ct[a[v]]]++;
}
int res[200005];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  set<int> vals;
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) cin >> a[i], vals.insert(a[i]), init[i] = a[i];
  set<int> aff;
  for (int i = 1; i <= q; ++i) {
    int ty;
    cin >> ty;
    if (ty == 1) {
      int l, r;
      cin >> l >> r;
      qq++;
      qr[qq] = make_pair(make_pair(l, r), make_pair(qu, qq));
    } else {
      int p, x;
      cin >> p >> x;
      vals.insert(x);
      aff.insert(p);
      upd[++qu] = make_pair(make_pair(p, x), a[p]);
      a[p] = x;
    }
  }
  if (!qq) return 0;
  map<int, int> comp;
  int st = 0;
  for (int v : vals) comp[v] = ++st;
  for (int i = 1; i <= n; ++i) a[i] = comp[init[i]], init[i] = a[i];
  for (int i = 1; i <= qu; ++i)
    upd[i].first.second = comp[upd[i].first.second],
    upd[i].second = comp[upd[i].second];
  sort(qr + 1, qr + qq + 1, cmp);
  for (int i = 1; i <= qq; ++i) {
    int l = qr[i].first.first, r = qr[i].first.second, tt = qr[i].second.first,
        ind = qr[i].second.second;
    while (tt < curtime) {
      int v = upd[curtime].first.first;
      if (v >= cl && v <= cr) {
        pres[ct[a[v]]]--;
        ct[a[v]]--;
        pres[ct[a[v]]]++;
        a[v] = upd[curtime].second;
        pres[ct[a[v]]]--;
        ct[a[v]]++;
        pres[ct[a[v]]]++;
      } else
        a[v] = upd[curtime].second;
      curtime--;
    }
    while (curtime < tt) {
      curtime++;
      int v = upd[curtime].first.first;
      if (v >= cl && v <= cr) {
        pres[ct[a[v]]]--;
        ct[a[v]]--;
        pres[ct[a[v]]]++;
        a[v] = upd[curtime].first.second;
        pres[ct[a[v]]]--;
        ct[a[v]]++;
        pres[ct[a[v]]]++;
      } else
        a[v] = upd[curtime].first.second;
    }
    while (cl < l) rmv(cl), cl++;
    while (cl > l) add(cl - 1), cl--;
    while (cr < r) add(cr + 1), cr++;
    while (cr > r) rmv(cr), cr--;
    int ans = 1;
    while (pres[ans]) ans++;
    res[ind] = ans;
  }
  for (int i = 1; i <= qq; ++i) cout << res[i] << '\n';
}