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("O3")
using namespace std;
inline int getint() {
  int _x = 0;
  char _tc = getchar();
  while (_tc < '0' || _tc > '9') _tc = getchar();
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x;
}
int _id;
unordered_map<int, int> map_to;
int Id(int x) {
  auto it = map_to.find(x);
  if (it != map_to.end()) return it->second;
  return map_to[x] = _id++;
}
int n, q, a[101010];
int cmd[101010], ql[101010], qr[101010], pr[101010];
vector<int> wt;
vector<int> rec[101010];
int cur[101010];
void init() {
  n = getint();
  q = getint();
  for (int i = 1; i <= n; i++) {
    a[i] = Id(getint());
    rec[i].push_back(a[i]);
  }
  for (int i = 0; i < q; i++) {
    cmd[i] = getint();
    ql[i] = getint();
    qr[i] = getint();
    if (cmd[i] == 2) {
      qr[i] = Id(qr[i]);
      rec[ql[i]].push_back(qr[i]);
      wt.push_back(ql[i]);
    } else
      pr[i] = wt.size();
  }
}
int ans[101010], mex[101010], cnt[101010 + 101010];
void modify(int pos, int dlt) {
  mex[cnt[a[pos]]]--;
  cnt[a[pos]] += dlt;
  mex[cnt[a[pos]]]++;
}
void change(int pos, int dlt, int cql, int cqr) {
  if (cql <= pos and pos <= cqr) modify(pos, -1);
  cur[pos] += dlt;
  a[pos] = rec[pos][cur[pos]];
  if (cql <= pos and pos <= cqr) modify(pos, +1);
}
void solve() {
  int k = 1;
  while ((long long)k * k * k <= (long long)n * n) k++;
  vector<pair<pair<int, int>, pair<int, int> > > qry;
  for (int i = 0; i < q; i++) {
    if (cmd[i] == 2) continue;
    qry.push_back({{ql[i] / k, pr[i] / k}, {qr[i], i}});
  }
  sort(qry.begin(), qry.end());
  modify(1, +1);
  int lb = 1, rb = 1, ch = 0;
  for (auto _ : qry) {
    int i = _.second.second;
    ans[i] = 1;
    while (lb > ql[i]) modify(--lb, +1);
    while (rb < qr[i]) modify(++rb, +1);
    while (lb < ql[i]) modify(lb++, -1);
    while (rb > qr[i]) modify(rb--, -1);
    while (ch < pr[i]) change(wt[ch++], +1, ql[i], qr[i]);
    while (ch > pr[i]) change(wt[--ch], -1, ql[i], qr[i]);
    while (mex[ans[i]]) ans[i]++;
  }
  for (int i = 0; i < q; i++) {
    if (cmd[i] == 2) continue;
    printf("%d\n", ans[i]);
  }
}
int main() {
  init();
  solve();
}