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;
inline int min(int x, int y) { return x < y ? x : y; }
inline int max(int x, int y) { return x > y ? x : y; }
typedef struct Seg* ntp;
ntp ta, rt;
struct Seg {
  ntp lc, rc;
  int l, r, mid, mins, maxs, pt, f1, f2;
  void build(int x, int y) {
    l = x, r = y, mid = (x + y) >> 1, pt = mins = maxs = 2000000000;
    if (l == r) return;
    lc = ++ta, lc->build(x, mid), rc = ++ta, rc->build(mid + 1, y);
  }
  inline void setf(int val, int fl) {
    if (!fl)
      f1 = val, mins = l - val, pt = maxs - val;
    else
      f2 = val, maxs = l + val, pt = mins + val;
  }
  inline void down(void) {
    if (f1) lc->setf(f1, 0), rc->setf(f1, 0), f1 = 0;
    if (f2) lc->setf(f2, 1), rc->setf(f2, 1), f2 = 0;
  }
  inline void upd(void) {
    mins = min(lc->mins, rc->mins), maxs = min(lc->maxs, rc->maxs);
    pt = min(lc->pt, rc->pt);
  }
  void modify(int x, int y, int val, int fl) {
    if (x <= l && r <= y) {
      setf(val, fl);
      return;
    }
    down();
    if (x <= mid) lc->modify(x, y, val, fl);
    if (y > mid) rc->modify(x, y, val, fl);
    upd();
  }
  int get(int val) {
    if (l == r) return pt <= val ? l : 2000000000;
    down();
    if (lc->pt <= val) return lc->get(val);
    if (rc->pt <= val) return rc->get(val);
    return 2000000000;
  }
} ua[210000 << 1];
map<int, int> gi;
int f[210000], g[210000], a[210000];
int n, m, d, L, R, ans, last;
int main(void) {
  scanf("%d%d%d", &n, &m, &d);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  if (!d) {
    for (int i = 1; i <= n; i++) {
      if (i - 1 && a[i] != a[i - 1]) last = i - 1;
      if (i - last > ans) ans = i - last, L = last + 1, R = i;
    }
    printf("%d %d\n", L, R);
    return 0;
  }
  rt = ta = ua, rt->build(1, n);
  for (int i = 1; i <= n; i++) {
    a[i] += 2000000000 / 2, last = max(last, gi[a[i]]), gi[a[i]] = i;
    if (i - 1 && (a[i - 1] - a[i]) % d) last = i - 1;
    while (*f && a[f[*f]] < a[i]) --*f;
    while (*g && a[g[*g]] > a[i]) --*g;
    rt->modify(f[*f] + 1, i, a[i] / d + 1, 1);
    rt->modify(g[*g] + 1, i, a[i] / d + 1, 0);
    f[++*f] = g[++*g] = i;
    if (last) rt->modify(1, last, 2000000000, 1);
    int li = rt->get(m + i);
    if (ans < i - li + 1) ans = i - li + 1, L = li, R = i;
  }
  printf("%d %d\n", L, R);
  return 0;
}
