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>
int read() {
  int ret = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f *= -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    ret = ret * 10 + c - '0';
    c = getchar();
  }
  return f * ret;
}
const int MAXN = 200000;
const int MAXT = MAXN * 20;
const int inf = 100001111;
int n;
namespace SegTree {
int sum[MAXT + 10];
int qmin[MAXT + 10], qmax[MAXT + 10];
int mintag[MAXT + 10], maxtag[MAXT + 10];
void tagmax(int x, int l, int max) {
  if (max < maxtag[x]) return;
  maxtag[x] = max;
  qmax[x] = l + max;
  sum[x] = qmin[x] + max;
  return;
}
void tagmin(int x, int l, int min) {
  if (min > mintag[x]) return;
  mintag[x] = min;
  qmin[x] = l - min;
  sum[x] = qmax[x] - min;
  return;
}
void down(int x, int l, int r) {
  if (maxtag[x] != -inf) {
    if (l != r) {
      int mid = (l + r) >> 1;
      tagmax(x << 1, l, maxtag[x]);
      tagmax(x << 1 | 1, mid + 1, maxtag[x]);
    }
    maxtag[x] = -inf;
  }
  if (mintag[x] != inf) {
    if (l != r) {
      int mid = (l + r) >> 1;
      tagmin(x << 1, l, mintag[x]);
      tagmin(x << 1 | 1, mid + 1, mintag[x]);
    }
    mintag[x] = inf;
  }
  return;
}
void update(int x) {
  qmin[x] = ((qmin[x << 1]) < (qmin[x << 1 | 1]) ? (qmin[x << 1])
                                                 : (qmin[x << 1 | 1]));
  qmax[x] = ((qmax[x << 1]) < (qmax[x << 1 | 1]) ? (qmax[x << 1])
                                                 : (qmax[x << 1 | 1]));
  sum[x] =
      ((sum[x << 1]) < (sum[x << 1 | 1]) ? (sum[x << 1]) : (sum[x << 1 | 1]));
  return;
}
void reset(int id, int q) {
  int x = 1, l = 1, r = n;
  while (l <= r) {
    down(x, l, r);
    if (l == r) break;
    int mid = (l + r) >> 1;
    if (id <= mid) {
      x <<= 1;
      r = mid;
    } else {
      x = (x << 1 | 1);
      l = mid + 1;
    }
  }
  sum[x] = id;
  qmax[x] = id + q;
  qmin[x] = id - q;
  while (x >> 1) update(x >>= 1);
  return;
}
void updatemin(int x, int l, int r, int ll, int rr, int min) {
  down(x, l, r);
  if (l == ll && r == rr) {
    tagmin(x, l, min);
    return;
  }
  int mid = (l + r) >> 1;
  if (rr <= mid)
    updatemin(x << 1, l, mid, ll, rr, min);
  else if (ll <= mid) {
    updatemin(x << 1, l, mid, ll, mid, min);
    updatemin(x << 1 | 1, mid + 1, r, mid + 1, rr, min);
  } else
    updatemin(x << 1 | 1, mid + 1, r, ll, rr, min);
  update(x);
  return;
}
void updatemax(int x, int l, int r, int ll, int rr, int max) {
  down(x, l, r);
  if (l == ll && r == rr) {
    tagmax(x, l, max);
    return;
  }
  int mid = (l + r) >> 1;
  if (rr <= mid)
    updatemax(x << 1, l, mid, ll, rr, max);
  else if (ll <= mid) {
    updatemax(x << 1, l, mid, ll, mid, max);
    updatemax(x << 1 | 1, mid + 1, r, mid + 1, rr, max);
  } else
    updatemax(x << 1 | 1, mid + 1, r, ll, rr, max);
  update(x);
  return;
}
int query(int x, int l, int r, int ll, int q) {
  down(x, l, r);
  if (sum[x] > q) return -1;
  if (l == r) return l;
  int mid = (l + r) >> 1;
  if (mid < ll)
    return query(x << 1 | 1, mid + 1, r, ll, q);
  else {
    int lans = query(x << 1, l, mid, ll, q);
    return (lans != -1) ? (lans) : (query(x << 1 | 1, mid + 1, r, ll, q));
  }
}
void build(int x, int l, int r) {
  mintag[x] = inf;
  maxtag[x] = -inf;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(x << 1, l, mid);
  build(x << 1 | 1, mid + 1, r);
  return;
}
}  // namespace SegTree
bool re;
std::map<int, int> cnt;
void modify(int id, int k) {
  if (cnt[id] == 1 && k == 1) re = true;
  if (cnt[id] == 2 && k == -1) re = false;
  cnt[id] += k;
  return;
}
int k, d;
int a[MAXN + 10];
int ansl, ansr;
void update(int l, int r) {
  if (!ansl || r - l > ansr - ansl || (r - l == ansr - ansl && ansl > l)) {
    ansl = l;
    ansr = r;
  }
  return;
}
int minsta[MAXN + 10], mintop;
int maxsta[MAXN + 10], maxtop;
void init() {
  n = read();
  k = read();
  d = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  if (d == 0) {
    for (int l = 1; l <= n;) {
      int r = l;
      while (r < n && a[r + 1] == a[r]) r++;
      update(l, r);
      l = r + 1;
    }
  } else {
    SegTree::build(1, 1, n);
    for (int l = 1; l <= n;) {
      int r = l;
      while (r < n && (a[r + 1] - a[r]) % d == 0) r++;
      for (int i = r; i >= l; i--) a[i] = (a[i] - a[l]) / d;
      minsta[mintop = 0] = maxsta[maxtop = 0] = l - 1;
      int ln = l;
      for (int rn = l; rn <= r; rn++) {
        while (mintop && a[minsta[mintop]] > a[rn]) mintop--;
        while (maxtop && a[maxsta[maxtop]] < a[rn]) maxtop--;
        modify(a[rn], 1);
        SegTree::reset(rn, a[rn]);
        SegTree::updatemin(1, 1, n, minsta[mintop] + 1, rn, a[rn]);
        SegTree::updatemax(1, 1, n, maxsta[maxtop] + 1, rn, a[rn]);
        while (re) modify(a[ln], -1), ln++;
        update(SegTree::query(1, 1, n, ln, rn + k), rn);
        minsta[++mintop] = maxsta[++maxtop] = rn;
      }
      while (ln <= r) modify(a[ln], -1), ln++;
      l = r + 1;
    }
  }
  std::cout << ansl << ' ' << ansr << std::endl;
  return;
}
int main() {
  init();
  return 0;
}
