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>
struct Query {
  int left;
  int right;
  int time;
  int index;
};
struct Change {
  int index;
  int value;
};
Change changes[100001];
Query queries[100001];
int numbers[100001];
int hash[200001];
int answers[100001];
int cnt[200001];
int cnt_of_cnt[100001];
int length;
int ans = 1;
int belong(int);
bool cmp(Query, Query);
void add(int);
void remove(int);
void change(int, int, int);
void change(int t, int left, int right) {
  if (changes[t].index >= left && changes[t].index <= right) {
    remove(numbers[changes[t].index]);
    add(changes[t].value);
  }
  std::swap(numbers[changes[t].index], changes[t].value);
}
void remove(int v) {
  cnt_of_cnt[cnt[v]]--;
  cnt[v]--;
  cnt_of_cnt[cnt[v]]++;
  if (cnt[v] + 1 && cnt[v] + 1 < ans && !cnt_of_cnt[cnt[v] + 1]) {
    ans = cnt[v] + 1;
  }
  if (cnt[v] && ans == cnt[v] && cnt_of_cnt[cnt[v]]) {
    for (; cnt_of_cnt[ans]; ans++)
      ;
  }
}
void add(int v) {
  cnt_of_cnt[cnt[v]]--;
  cnt[v]++;
  cnt_of_cnt[cnt[v]]++;
  if (cnt[v] - 1 && cnt[v] - 1 < ans && !cnt_of_cnt[cnt[v] - 1]) {
    ans = cnt[v] - 1;
  }
  if (cnt[v] && ans == cnt[v] && cnt_of_cnt[cnt[v]]) {
    for (; cnt_of_cnt[ans]; ans++)
      ;
  }
}
bool cmp(Query a, Query b) {
  if (belong(a.left) == belong(b.left)) {
    if (belong(a.right) == belong(b.right)) {
      return a.time < b.time;
    } else {
      return a.right < b.right;
    }
  } else {
    return belong(a.left) < belong(b.left);
  }
}
int belong(int x) { return (x + length - 1) / length; }
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  int n, m;
  std::cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    std::cin >> numbers[i];
    hash[i] = numbers[i];
  }
  int change = 0;
  int query = 0;
  for (int i = 1; i <= m; i++) {
    int op;
    std::cin >> op;
    if (op == 2) {
      change++;
      std::cin >> changes[change].index >> changes[change].value;
      hash[n + change] = changes[change].value;
    } else {
      query++;
      std::cin >> queries[query].left >> queries[query].right;
      queries[query].index = query;
      queries[query].time = change;
    }
  }
  std::sort(hash + 1, hash + 1 + n + change);
  int top = std::unique(hash + 1, hash + 1 + n + change) - hash - 1;
  for (int i = 1; i <= n; i++) {
    numbers[i] = std::lower_bound(hash + 1, hash + 1 + top, numbers[i]) - hash;
  }
  for (int i = 1; i <= change; i++) {
    changes[i].value =
        std::lower_bound(hash + 1, hash + 1 + top, changes[i].value) - hash;
  }
  length = std::pow(n, 0.67) + 1;
  std::sort(queries + 1, queries + 1 + query, cmp);
  int left = 1;
  int right = 0;
  int time = 0;
  for (int i = 1; i <= query; i++) {
    while (left > queries[i].left) {
      left--;
      add(numbers[left]);
    }
    while (right < queries[i].right) {
      right++;
      add(numbers[right]);
    }
    while (left < queries[i].left) {
      remove(numbers[left]);
      left++;
    }
    while (right > queries[i].right) {
      remove(numbers[right]);
      right--;
    }
    while (time < queries[i].time) {
      time++;
      ::change(time, left, right);
    }
    while (time > queries[i].time) {
      ::change(time, left, right);
      time--;
    }
    answers[queries[i].index] = ans;
  }
  for (int i = 1; i <= query; i++) {
    std::cout << answers[i] << '\n';
  }
  return 0;
}