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 INF = 0x3f3f3f3f;
const int MAXN = 2e5 + 5;
int n, k, d, ansL = 1, ansR = 1, top1, top2;
int a[MAXN], st1[MAXN], st2[MAXN];
map<int, int> lst;
namespace SegmentTree {
struct Tree {
  int l, r;
  int w, tag;
} tree[MAXN << 2];
void update(int k) { tree[k].w = min(tree[k << 1].w, tree[k << 1 | 1].w); }
void apply(int k, int val) {
  tree[k].w += val;
  tree[k].tag += val;
}
void down(int k) {
  if (tree[k].tag != 0) {
    apply(k << 1, tree[k].tag);
    apply(k << 1 | 1, tree[k].tag);
    tree[k].tag = 0;
  }
}
void Build(int k, int l, int r) {
  tree[k].l = l;
  tree[k].r = r;
  if (l == r) {
    tree[k].w = l;
    return;
  }
  int mid = (l + r) >> 1;
  Build(k << 1, l, mid);
  Build(k << 1 | 1, mid + 1, r);
  update(k);
}
void Modify(int k, int l, int r, int val) {
  if (tree[k].l >= l && tree[k].r <= r) {
    apply(k, val);
    return;
  }
  down(k);
  int mid = (tree[k].l + tree[k].r) >> 1;
  if (l <= mid) Modify(k << 1, l, r, val);
  if (r > mid) Modify(k << 1 | 1, l, r, val);
  update(k);
}
void Delete(int k, int x) {
  if (tree[k].l == tree[k].r) {
    tree[k].w = INF;
    return;
  }
  down(k);
  int mid = (tree[k].l + tree[k].r) >> 1;
  if (x <= mid)
    Delete(k << 1, x);
  else
    Delete(k << 1 | 1, x);
  update(k);
}
int Query(int k, int l, int r, int x) {
  if (tree[k].w > x) return INF;
  if (tree[k].l == tree[k].r) return tree[k].l;
  if (tree[k].l >= l && tree[k].r <= r) {
    down(k);
    if (tree[k << 1].w <= x)
      return Query(k << 1, l, r, x);
    else
      return Query(k << 1 | 1, l, r, x);
  } else {
    down(k);
    int mid = (tree[k].l + tree[k].r) >> 1;
    int res;
    if (l <= mid) {
      res = Query(k << 1, l, r, x);
      if (res != INF) return res;
    }
    if (r > mid) {
      res = Query(k << 1 | 1, l, r, x);
      if (res != INF) return res;
    }
    return -1;
  }
}
}  // namespace SegmentTree
int main() {
  scanf("%d%d%d", &n, &k, &d);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    a[i] += INF;
  }
  if (d == 0) {
    for (int i = 1; i <= n; i++) {
      int l = i;
      while (a[i] == a[i + 1] && i < n) i += 1;
      if (i - l + 1 > ansR - ansL + 1) {
        ansL = l;
        ansR = i;
      }
    }
    printf("%d %d\n", ansL, ansR);
    return 0;
  }
  SegmentTree::Build(1, 1, n);
  int L = 1;
  for (int R = 1; R <= n; R++) {
    int tmp = L;
    if (a[R] % d == a[R - 1] % d)
      L = max(lst[a[R]] + 1, L);
    else
      L = R;
    lst[a[R]] = R;
    while (tmp < L) {
      SegmentTree::Delete(1, tmp);
      tmp += 1;
    }
    while (top1 && st1[top1] >= L && a[st1[top1]] >= a[R]) {
      SegmentTree::Modify(1, max(L, st1[top1 - 1] + 1), st1[top1],
                          a[st1[top1]] / d);
      top1 -= 1;
    }
    SegmentTree::Modify(1, max(L, st1[top1] + 1), R, -a[R] / d);
    st1[++top1] = R;
    while (top2 && st2[top2] >= L && a[st2[top2]] <= a[R]) {
      SegmentTree::Modify(1, max(L, st2[top2 - 1] + 1), st2[top2],
                          -a[st2[top2]] / d);
      top2 -= 1;
    }
    SegmentTree::Modify(1, max(L, st2[top2] + 1), R, a[R] / d);
    st2[++top2] = R;
    int pos = SegmentTree::Query(1, L, R, k + R);
    if (R - pos + 1 > ansR - ansL + 1) {
      ansL = pos;
      ansR = R;
    }
  }
  printf("%d %d\n", ansL, ansR);
  return 0;
}
