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;
int adv[200010 * 5], mn[200010 * 5], n, k, d, t[200010], al, ar, bc[200010],
    c[200010], s1[200010], s2[200010], t1, t2, b[200010], a[200010];
void pd(int o) {
  if (adv[o]) {
    adv[o * 2] += adv[o];
    adv[o * 2 + 1] += adv[o];
    mn[o * 2] += adv[o];
    mn[o * 2 + 1] += adv[o];
    adv[o] = 0;
  }
}
void up(int o) { mn[o] = min(mn[o * 2], mn[o * 2 + 1]); }
void add(int o, int l, int r, int x, int y, int z) {
  if (r < x || y < l) return;
  if (x <= l && r <= y) {
    adv[o] += z;
    mn[o] += z;
    return;
  }
  int md = (l + r) / 2;
  pd(o);
  add(o * 2, l, md, x, y, z);
  add(o * 2 + 1, md + 1, r, x, y, z);
  up(o);
}
int ans;
int fd(int o, int l, int r, int v) {
  if (mn[o] > v) return 0;
  if (l == r) return l;
  pd(o);
  int md = (l + r) / 2;
  if (mn[o * 2] <= v)
    return fd(o * 2, l, md, v);
  else
    return fd(o * 2 + 1, md + 1, r, v);
}
void q(int o, int l, int r, int x, int y, int v) {
  if (r < x || y < l) return;
  if (x <= l && r <= y) {
    if (!ans) ans = fd(o, l, r, v);
    return;
  }
  int md = (l + r) / 2;
  pd(o);
  q(o * 2, l, md, x, y, v);
  q(o * 2 + 1, md + 1, r, x, y, v);
}
void bd(int o, int l, int r) {
  adv[o] = mn[o] = 0;
  if (l == r) return;
  int md = (l + r) / 2;
  bd(o * 2, l, md);
  bd(o * 2 + 1, md + 1, r);
}
void gt(int x) {
  s1[t1 = 1] = s2[t2 = 1] = 0;
  int ls = 1;
  bd(1, 1, *c);
  for (int i = 1; i <= *c; i++) {
    for (; t1 > 1 && c[s1[t1]] <= c[i]; t1--)
      add(1, 1, *c, s1[t1 - 1] + 1, s1[t1], c[i] - c[s1[t1]]);
    s1[++t1] = i;
    for (; t2 > 1 && c[s2[t2]] >= c[i]; t2--)
      add(1, 1, *c, s2[t2 - 1] + 1, s2[t2], c[s2[t2]] - c[i]);
    s2[++t2] = i;
    add(1, 1, *c, i, i, i);
    ls = max(ls, bc[b[i + x - 1]] + 1);
    bc[b[i + x - 1]] = i;
    ans = 0;
    q(1, 1, *c, ls, i, i + k);
    if (ar - al < i - ans) {
      al = x + ans - 1;
      ar = i + x - 1;
    }
  }
  for (int i = 1; i <= *c; i++) bc[b[i + x - 1]] = 0;
}
int main() {
  ar = -1;
  scanf("%d%d%d", &n, &k, &d);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    t[i] = a[i];
  }
  if (!d) {
    int j = 1;
    for (int i = 1; i <= n;) {
      while (a[j + 1] == a[i] && j < n) j++;
      if (ar - al < j - i) {
        ar = j;
        al = i;
      }
      i = j + 1;
    }
    printf("%d %d", al, ar);
    return 0;
  }
  sort(t + 1, t + n + 1);
  int v = unique(t + 1, t + n + 1) - t - 1;
  for (int i = 1; i <= n; i++) b[i] = lower_bound(t + 1, t + v + 1, a[i]) - t;
  int j = 1;
  for (int i = 1; i <= n;) {
    *c = 0;
    while ((a[j + 1] % d + d) % d == (a[i] % d + d) % d && j < n) j++;
    for (int k = i; k <= j; k++) c[++*c] = a[k] / d;
    gt(i);
    i = j + 1;
  }
  printf("%d %d", al, ar);
}
