Нолик и игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
different.in
вывод
different.out

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

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

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

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

В первой строке входного файла находятся три целых числа n, m, k (1 ≤ n ≤ 105, 1 ≤ m ≤ 105, 1 ≤ k ≤ n) — количество кубиков, расположенных в ряд, количество событий в игре и длина отрезка. В следущей строке находятся n чисел ai (1 ≤ ai ≤ 106) — цвета кубиков в начальный момент времени.

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

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

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

Примеры тестов

Входные данные
5 3 3
1 2 1 3 3
2 1 3
1 3 3
2 1 5
Выходные данные
2
3
Входные данные
6 6 3
2 3 1 1 1 9
2 1 3
2 3 5
1 3 3
2 1 5
1 2 1
2 1 6
Выходные данные
3
1
2
3