F. Машинное обучение
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы чувствуете неприятный запах. Откуда же он?

Дан массив a. Вам нужно уметь отвечать на следующие запросы:

  1. Даны целые числа l и r. Пусть ci  — количество вхождений числа i в al: r, где al: r — это подмассив a с l-го элемента по r-й включительно. Найдите Mex множества {c0, c1, ..., c109}.
  2. Даны целые числа p и x. Присвойте ap значение x.

Mex мультимножества чисел это минимальное неотрицательное целое число, не входящее в множество.

Обратите внимание, что в данной задаче элементы a положительные, соответственно c0 = 0, поэтому 0 никогда не является ответом на запрос второго типа.

Входные данные

Первая строка содержит n и q (1 ≤ n, q ≤ 100 000) — размер массива и число запросов соответственно.

Во второй строке записано ровно n чисел — a1, a2, ..., an (1 ≤ ai ≤ 109).

Каждая из оставшихся q строк задаёт очередной запрос.

Запрос первого типа задаётся тремя числами ti = 1, li, ri, где 1 ≤ li ≤ ri ≤ n — границы соответствующего подмассива.

Запрос второго типа задаётся тремя числами ti = 2, pi, xi, где 1 ≤ pi ≤ n — позиция в которой нужно заменить число, а 1 ≤ xi ≤ 109 — его новое значение.

Выходные данные

Для каждого запроса первого типа выведите одно число — Mex множества {c0, c1, ..., c109}.

Пример
Входные данные
10 4
1 2 3 1 1 2 2 2 9 9
1 1 1
1 2 8
2 7 1
1 2 8
Выходные данные
2
3
2
Примечание

Отрезок первого запрос состоит из ровно одного элемента — 1.

Отрезок второго запроса состоит из четырёх 2, одной 3 и двух 1.

Отрезок четвёртого запроса состоит из трёх 1, трёх 2 и одной 3.