题目描述

鬼鬼是一个十四岁的少女，她特别喜欢等差数列。出于对等差数列的喜欢，她想找这种序列：向这个序列$\red{a}$中加上 不多于$\red{k}$个数，使这个新的数列排序后可以得到一个公差为$\red{d}$的等差序列。

鬼鬼给你了一个由$\red{n}$个整数组成的数列$\red{a}$。你的任务是找到它的最长子串，使它是鬼鬼想找的序列。鬼鬼会十分感 谢你的！

输入格式

第一行输入三个整数 $\red{n,k,d}$。（$\red{1<=n<=2e5, 0<=k<=2e5, 0<=d<=1e9）}$

第二行输入 $\red{n }$个整数，表示数列$\red{a[]}$。（$\red{-1e9 <=a[i] <=1e9）}$

输出格式

输出两个整数 $\red{L,R，}$描述这个最长子串的左$\red{/}$右边界。如果有多个最优答案，输出 $\red{L }$值最小的。

样例

输入样例

6 1 2
4 3 2 8 6 2

输出样例

3 5

提示

样例解释

第一个测试样例的答案为包括数字$\red{2，}$$\red{8 ，}$$\red{6 }$的子串——在加入数字$\red{4}$并且 排序之后，它变成了数列$\red{2，}$$\red{4，}$$\red{6，}$$\red{8 }$——公差为$\red{2}$的等差数列。