N. Гномы
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

После освобождения Земли Гномов от нечисти Светозар был единогласно избран администратором, которому теперь решать, как лучше организовать защиту от злых магов.

На следующем всеобщем собрании все гномы выстроились в ряд. У гнома с номером $$$i$$$ в ряду на голове надета шапка цвета $$$a_i$$$. Светозар хочет выбрать несколько подряд идущих гномов в Совет Земли Гномов. Но если строго больше половины гномов в Совете будут с шапками одинакового цвета, то у них сформируется абсолютное большинство. К каким последствиям может привести наличие абсолютного большинства, Светозар пока не знает, но заранее этого опасается.

Пока что Светозар лишь размышляет, каких гномов выбрать. Периодически он задаёт вам один из двух типов вопросов:

  • $$$1$$$ $$$p$$$ $$$x$$$: поменять цвет шапки гнома с номером $$$p$$$ на цвет $$$x$$$;
  • $$$2$$$ $$$\ell$$$ $$$r$$$: найти цвет $$$x$$$, который составляет абсолютное большинство среди гномов с номерами от $$$\ell$$$ до $$$r$$$ включительно, либо сказать, что такого нет.
Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leqslant n, q \leqslant 2 \cdot 10^5$$$) — количество гномов и количество вопросов Светозара.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leqslant a_i \leqslant 10^9$$$) — цвета шапок гномов.

Далее следуют $$$q$$$ вопросов, по одному в строке, в одном из двух форматов, описанных выше:

  • $$$1$$$ $$$p$$$ $$$x$$$ ($$$1 \leqslant p \leqslant n$$$, $$$1 \leqslant x \leqslant 10^9$$$);
  • $$$2$$$ $$$\ell$$$ $$$r$$$ ($$$1 \leqslant \ell \leqslant r \leqslant n$$$).
Выходные данные

Для каждого вопроса второго типа выведите одно целое число — цвет абсолютного большинства для заданного набора гномов или $$$-1$$$, если такого цвета нет.

Пример
Входные данные
6 10
1 1 2 3 4 4
2 1 4
2 1 3
2 2 5
2 5 6
1 3 1
2 1 3
2 3 6
1 6 1
2 1 6
2 4 5
Выходные данные
-1
1
-1
4
1
-1
1
-1
Примечание

После вопросов первого типа цвета шапок гномов будут выглядеть как $$$(1, 1, 1, 3, 4, 4)$$$ и $$$(1, 1, 1, 3, 4, 1)$$$ соответственно.