We'll call a sequence of integers a good k-d sequence if we can add to it at most k numbers in such a way that after the sorting the sequence will be an arithmetic progression with difference d.

You got hold of some sequence a, consisting of n integers. Your task is to find its longest contiguous subsegment, such that it is a good k-d sequence.

Input

The first line contains three space-separated integers n, k, d (1 ≤ n ≤ 2·105; 0 ≤ k ≤ 2·105; 0 ≤ d ≤ 109). The second line contains n space-separated integers: a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the actual sequence.

Output

Print two space-separated integers l, r (1 ≤ l ≤ r ≤ n) show that sequence al, al + 1, ..., ar is the longest subsegment that is a good k-d sequence.

If there are multiple optimal answers, print the one with the minimum value of l.

Examples

Input

6 1 2
4 3 2 8 6 2


Output

3 5

Note

In the first test sample the answer is the subsegment consisting of numbers 2, 8, 6 — after adding number 4 and sorting it becomes sequence 2, 4, 6, 8 — the arithmetic progression with difference 2.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005, INF = -1e9;
int N_seg, ch[maxn * 2][2];
long long Min[maxn * 2], tag[maxn * 2];
void Plus(int p, long long val) {
  Min[p] += val;
  tag[p] += val;
}
void maintain(int p) { Min[p] = min(Min[ch[p][0]], Min[ch[p][1]]); }
void pushdown(int p) {
  if (tag[p]) Plus(ch[p][0], tag[p]), Plus(ch[p][1], tag[p]), tag[p] = 0;
}
int Build(int L, int R) {
  int p = ++N_seg;
  tag[p] = 0;
  ch[p][0] = ch[p][1] = 0;
  if (L == R) return Min[p] = -L, p;
  int mid = (L + R) >> 1;
  ch[p][0] = Build(L, mid);
  ch[p][1] = Build(mid + 1, R);
  maintain(p);
  return p;
}
void Update(int p, int L, int R, int qL, int qR, int val) {
  if (R < qL || qR < L) return;
  if (qL <= L && R <= qR) return Plus(p, val);
  int mid = (L + R) >> 1;
  pushdown(p);
  Update(ch[p][0], L, mid, qL, qR, val);
  Update(ch[p][1], mid + 1, R, qL, qR, val);
  maintain(p);
}
int Query(int p, int L, int R, int qL, int qR, int val) {
  if (R < qL || qR < L || Min[p] > val) return INF;
  if (L == R) return L;
  int mid = (L + R) >> 1;
  pushdown(p);
  int t = Query(ch[p][1], mid + 1, R, qL, qR, val);
  if (t > INF) return t;
  return Query(ch[p][0], L, mid, qL, qR, val);
}
int n, K, D, _a[maxn], a[maxn], b[maxn], stk1[maxn], stk2[maxn], top1, top2;
int ansL, ansR;
map<int, int> M;
void Solve(int L, int R) {
  N_seg = 0;
  Build(L, R);
  M.clear();
  stk1[0] = stk2[0] = R + 1;
  top1 = top2 = 0;
  int lst = R;
  for (int i = R; i >= L; i--) {
    while (top1 && a[i] > a[stk1[top1]]) {
      Update(1, L, R, stk1[top1], stk1[top1 - 1] - 1, -a[stk1[top1]]), top1--;
    }
    Update(1, L, R, i, stk1[top1] - 1, a[i]);
    stk1[++top1] = i;
    while (top2 && a[i] < a[stk2[top2]]) {
      Update(1, L, R, stk2[top2], stk2[top2 - 1] - 1, a[stk2[top2]]), top2--;
    }
    Update(1, L, R, i, stk2[top2] - 1, -a[i]);
    stk2[++top2] = i;
    if (M[_a[i]]) lst = min(lst, M[_a[i]] - 1);
    M[_a[i]] = i;
    int res = Query(1, L, R, i, lst, K - i);
    if (res - i + 1 > ansR - ansL + 1 ||
        (res - i + 1 == ansR - ansL + 1 && i < ansL))
      ansL = i, ansR = res;
  }
}
int main() {
  scanf("%d%d%d", &n, &K, &D);
  for (int i = 1; i <= n; i++) scanf("%d", &_a[i]), a[i] = _a[i];
  if (D == 0) {
    ansL = 1e9;
    ansR = 0;
    for (int i = 1, j; i <= n; i = j) {
      j = i;
      while (j <= n && _a[i] == _a[j]) j++;
      Solve(i, j - 1);
      if (j - i > ansR - ansL + 1 || (j - i == ansR - ansL + 1 && i < ansL))
        ansL = i, ansR = j - 1;
    }
    printf("%d %d\n", ansL, ansR);
    return 0;
  }
  for (int i = 1; i <= n; i++) b[i] = (a[i] % D + D) % D, a[i] /= D;
  ansL = 1e9;
  ansR = 0;
  for (int i = 1, j; i <= n; i = j) {
    j = i;
    while (j <= n && b[i] == b[j]) j++;
    Solve(i, j - 1);
  }
  printf("%d %d\n", ansL, ansR);
  return 0;
}
