Нолик и игра

Нолик обнаружил на телефоне Дим Димыча одну занимательную игру. Эта игра по задумке ее создателей должна тренировать реакцию и внимательность. Но для Дим Димыча она слишком сложна.

Игра состоит в следующем. На экране телефона расположены $n$ цветных кубиков, которые стоят в один ряд. В некоторые моменты времени цвета некоторых кубиков меняются. А также, иногда игра задает вопрос играющему: она говорит ему некоторый интервал $[l \dots r]$ ($1 \le l \le r \le n$), а играющий должен ответить --- какое максимальное количество различных цветов находится на некотором отрезке длины $k$, содержащемся в $[l \dots r]$. Число $k$ генерируется в начале игры и остается постоянным на всем ее протяжении. Цель игры заключается в том, чтобы правильно ответить на все вопросы игры.

Вам предлагается побыть в роле программиста этой игры и посчитать правильные ответы на все вопросы.

В первой строке входного файла находятся три целых числа $n, m, k$ ($1 \le n \le 10^5, 1 \le m \le 10^5, 1 \le k \le n$) --- количество кубиков, расположенных в ряд, количество событий в игре и длина отрезка. В следущей строке находятся $n$ чисел $a_i$ ($1 \le a_i \le 10^6$) --- цвета кубиков в начальный момент времени.

В следующих $m$ строках находятся описания событий игры --- по одному в строке:

• 1 i x --- изменить цвет $i$-го ($1 \le i \le n$) кубика на цвет $x$ ($1 \le x \le 10^6$);
• 2 l r --- ответить на вопрос: какое максимальное количество различных цветов находится на некотором отрезке длины $k$, содержащемся в $[l \dots r]$, $r - l + 1 \ge k$.

Выведите ответы на вопросы игры по одному в строке в том порядке, в котором они задаются игрой.