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;
void Read(int &p) {
  p = 0;
  int f = 0;
  char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) f |= (c == '-');
  for (; c >= '0' && c <= '9'; c = getchar()) p = p * 10 + c - '0';
  if (f) p = -p;
}
int n, d, k, A[200005];
int lst[200005], ans;
int stk1[200005], top1;
int stk2[200005], top2;
pair<int, int> V[200005];
struct SGT {
  int laz, mnn, l, r;
} S[200005 << 2];
void Pushup(int q) { S[q].mnn = min(S[q << 1].mnn, S[q << 1 | 1].mnn); }
void Pushdown(int q) {
  if (S[q].laz) {
    S[q << 1].mnn += S[q].laz;
    S[q << 1 | 1].mnn += S[q].laz;
    S[q << 1].laz += S[q].laz;
    S[q << 1 | 1].laz += S[q].laz;
  }
  S[q].laz = 0;
}
void Build(int q, int l, int r) {
  S[q].l = l, S[q].r = r;
  int mid = (l + r) >> 1;
  if (l == r) {
    S[q].mnn = l;
    return;
  }
  Build(q << 1, l, mid);
  Build(q << 1 | 1, mid + 1, r);
  Pushup(q);
}
void Modify(int q, int L, int R, int v) {
  if (S[q].l >= L && S[q].r <= R) {
    S[q].mnn += v;
    S[q].laz += v;
    return;
  }
  int mid = (S[q].l + S[q].r) >> 1;
  Pushdown(q);
  if (L <= mid) Modify(q << 1, L, R, v);
  if (R > mid) Modify(q << 1 | 1, L, R, v);
  Pushup(q);
}
int Query(int q, int v) {
  if (S[q].mnn > v) return 0;
  if (S[q].l == S[q].r) return S[q].l;
  Pushdown(q);
  if (S[q << 1].mnn <= v) return Query(q << 1, v);
  return Query(q << 1 | 1, v);
}
void Find(int q, int L, int R, int v) {
  if (S[q].l >= L && S[q].r <= R) {
    if (!ans) ans = Query(q, v);
    return;
  }
  int mid = (S[q].l + S[q].r) >> 1;
  Pushdown(q);
  if (L <= mid) Find(q << 1, L, R, v);
  if (R > mid) Find(q << 1 | 1, L, R, v);
}
int main() {
  Read(n), Read(k), Read(d);
  for (int i = 1; i <= n; i++) Read(A[i]);
  if (!d) {
    int ans = 0;
    for (int i = n; i >= 1; i--) {
      if (A[i] == A[i + 1])
        lst[i] = lst[i + 1];
      else
        lst[i] = i;
      ans = max(ans, lst[i] - i);
    }
    for (int i = 1; i <= n; i++)
      if (lst[i] - i == ans) {
        printf("%d %d\n", i, lst[i]);
        break;
      }
    return 0;
  }
  for (int i = 1; i <= n; i++) V[i] = make_pair(A[i], i);
  sort(V + 1, V + n + 1);
  for (int i = 2; i <= n; i++)
    if (V[i - 1].first == V[i].first) lst[V[i].second] = V[i - 1].second;
  Build(1, 1, n);
  int lef = 0;
  int u = 1, v = 0;
  for (int i = 1; i <= n; i++) {
    if (i == 1 || (A[i] % d + d) % d != (A[i - 1] % d + d) % d)
      top1 = top2 = 0, lef = i;
    while (top1 && A[stk1[top1]] < A[i]) {
      Modify(1, stk1[top1 - 1] + 1, stk1[top1], (A[i] - A[stk1[top1]]) / d);
      top1--;
    }
    stk1[++top1] = i;
    while (top2 && A[stk2[top2]] > A[i]) {
      Modify(1, stk2[top2 - 1] + 1, stk2[top2], (A[stk2[top2]] - A[i]) / d);
      top2--;
    }
    stk2[++top2] = i;
    lef = max(lef, lst[i] + 1);
    ans = 0;
    Find(1, lef, i, i + k);
    if (i - ans > v - u) u = ans, v = i;
  }
  printf("%d %d\n", u, v);
}
