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>
#pragma comment(linker, "/STACK:500000000")
using namespace std;
int A[200005];
int B[200005];
int mod[200005];
int maxR[200005];
map<int, int> q;
int n;
int Tree[4 * 200005];
int ADD[4 * 200005];
void updateTree(int node, int tl, int tr, int l, int r, int add) {
  if (l > r) return;
  if (l == tl && r == tr) {
    ADD[node] += add;
  } else {
    int tm = (tl + tr) / 2;
    updateTree(node << 1, tl, tm, l, min(r, tm), add);
    updateTree((node << 1) + 1, tm + 1, tr, max(tm + 1, l), r, add);
    Tree[node] = min(Tree[node << 1] + ADD[node << 1],
                     Tree[(node << 1) + 1] + ADD[(node << 1) + 1]);
  }
}
int getMin(int node, int tl, int tr, int l, int r) {
  if (l > r) return (2e9 + 100000);
  if (l == tl && r == tr)
    return Tree[node] + ADD[node];
  else {
    int tm = (tl + tr) >> 1;
    return ADD[node] +
           min(getMin(node << 1, tl, tm, l, min(r, tm)),
               getMin((node << 1) + 1, tm + 1, tr, max(l, tm + 1), r));
  }
}
struct segment {
  segment() {}
  segment(int L, int R, int value) : L(L), R(R), value(value) {}
  int L, R, value;
};
int maxLen = 0, minLen = 0;
segment maxStack[200005], minStack[200005];
int f(int l, int r, int k) {
  int L = l;
  int R = r;
  int res = l - 1;
  while (L <= R) {
    int m = (L + R) / 2;
    int minV = getMin(1, 0, n - 1, m, r);
    if (minV <= k)
      L = m + 1, res = m;
    else
      R = m - 1;
  }
  return res;
}
int main() {
  int k, d, i;
  int ansL = 0, ansR = 0;
  cin >> n >> k >> d;
  for (i = 0; i < n; i++) scanf("%d", &A[i]), A[i] += 1e9;
  if (d == 0) {
    for (i = 0; i < n;) {
      int j = i;
      while (j < n && A[j] == A[i]) j++;
      if (j - 1 - i > ansR - ansL) ansL = i, ansR = j - 1;
      i = j;
    }
    printf("%d %d\n", ansL + 1, ansR + 1);
    return 0;
  }
  for (i = 0; i < n; i++) {
    B[i] = A[i] / d;
    mod[i] = (A[i] % d + d) % d;
  }
  q[B[n - 1]] = n - 1;
  maxR[n - 1] = n - 1;
  for (i = n - 2; i >= 0; i--) {
    if (mod[i] == mod[i + 1] &&
        (q.find(B[i]) == q.end() || q[B[i]] > maxR[i + 1]))
      maxR[i] = maxR[i + 1];
    else if (mod[i] == mod[i + 1])
      maxR[i] = q[B[i]] - 1;
    else
      maxR[i] = i;
    q[B[i]] = i;
  }
  ansL = ansR = n - 1;
  maxStack[maxLen++] = (segment(n - 1, n - 1, B[n - 1]));
  minStack[minLen++] = (segment(n - 1, n - 1, B[n - 1]));
  for (int L = n - 2; L >= 0; L--) {
    int R = L;
    while (maxLen && maxStack[maxLen - 1].value <= B[L]) {
      int topValue = maxStack[maxLen - 1].value;
      int Left = maxStack[maxLen - 1].L;
      int Right = maxStack[maxLen - 1].R;
      while (maxLen && maxStack[maxLen - 1].value == topValue) {
        Right = max(Right, maxStack[maxLen - 1].L);
        maxLen--;
      }
      updateTree(1, 0, n - 1, Left, Right, B[L] - topValue);
      R = max(R, Right);
    }
    maxStack[maxLen++] = (segment(L, R, B[L]));
    R = L;
    while (minLen && minStack[minLen - 1].value >= B[L]) {
      int topValue = minStack[minLen - 1].value;
      int Left = minStack[minLen - 1].L;
      int Right = minStack[minLen - 1].R;
      while (minLen && minStack[minLen - 1].value == topValue) {
        Right = max(Right, minStack[minLen - 1].L);
        minLen--;
      }
      updateTree(1, 0, n - 1, Left, Right, topValue - B[L]);
      R = max(R, Right);
    }
    minStack[minLen++] = (segment(L, R, B[L]));
    updateTree(1, 0, n - 1, L + 1, n - 1, -1);
    R = f(L + 1, maxR[L], k);
    if (R - L >= ansR - ansL) ansL = L, ansR = R;
  }
  printf("%d %d\n", ansL + 1, ansR + 1);
}
