E. k-d-последовательность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем последовательность целых чисел хорошей k-d-последовательностью, если в нее можно добавить не более k чисел так, что после сортировки последовательность станет арифметической прогрессией с разностью d.

К вам в руки попала некая последовательность a, состоящая из n целых чисел. Вам требуется найти наидлиннейший непрерывный ее подотрезок, такой, что он является хорошей k-d-последовательностью.

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

В первой строке записаны через пробел три целых числа n, k, d (1 ≤ n ≤ 2·105; 0 ≤ k ≤ 2·105; 0 ≤ d ≤ 109). Во второй строке записаны n целых чисел через пробел: a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — сама последовательность.

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

Выведите через пробел два целых числа l, r (1 ≤ l ≤ r ≤ n), которые обозначают, что последовательность al, al + 1, ..., ar — наидлиннейший подотрезок, являющийся хорошей k-d-последовательностью.

Если существует несколько оптимальных вариантов ответа, выведите ответ c наименьшим значением l.

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

В первом тестовом примере ответом является отрезок, состоящий из чисел 2, 8, 6 — после добавления числа 4 и сортировки он превращается в последовательность 2, 4, 6, 8 — арифметическую прогрессию с разностью 2.