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 N = 200005;
struct P {
  int l, r, mid, add, mi;
} arr[4 * N];
void down(int c) {
  if (arr[c].add) {
    arr[c + c].add += arr[c].add;
    arr[c + c + 1].add += arr[c].add;
    arr[c].add = 0;
  }
}
void build(int L, int R, int c) {
  arr[c].l = L;
  arr[c].r = R;
  arr[c].mid = (L + R) / 2;
  if (L == R) {
    arr[c].mi = L;
    return;
  }
  build(L, arr[c].mid, c + c);
  build(arr[c].mid + 1, R, c + c + 1);
  arr[c].mi = min(arr[c + c].mi, arr[c + c + 1].mi);
}
void add(int L, int R, int v, int c) {
  if (L <= arr[c].l && R >= arr[c].r) {
    arr[c].add += v;
    return;
  }
  down(c);
  if (L <= arr[c].mid) add(L, R, v, c + c);
  if (R > arr[c].mid) add(L, R, v, c + c + 1);
  arr[c].mi = min(arr[c + c].mi + arr[c + c].add,
                  arr[c + c + 1].mi + arr[c + c + 1].add);
}
int find(int L, int R, int v, int c, int tp) {
  if (!tp) {
    if (L <= arr[c].l && R >= arr[c].r) {
      if (arr[c].mi + arr[c].add > v) return N;
      tp = 1;
    }
  }
  if (tp) {
    if (arr[c].l == arr[c].r) return arr[c].l;
  }
  int r = N;
  down(c);
  if ((!tp && L <= arr[c].mid) || (tp && arr[c + c].mi + arr[c + c].add <= v))
    r = find(L, R, v, c + c, tp);
  if (r == N && R > arr[c].mid) r = find(L, R, v, c + c + 1, tp);
  arr[c].mi = min(arr[c + c].mi + arr[c + c].add,
                  arr[c + c + 1].mi + arr[c + c + 1].add);
  return r;
}
map<int, int> lzs;
int q1[N], q2[N], pre[N], t1, t2, a[N], b[N], rr, rl, k;
void work(int L, int R) {
  t1 = t2 = 0;
  int i;
  int pe = 0;
  for (i = L; i <= R; i++) {
    while (t1 && b[q1[t1]] >= b[i]) {
      add(q1[t1 - 1] + 1, q1[t1], b[q1[t1]], 1);
      t1--;
    }
    while (t2 && b[q2[t2]] <= b[i]) {
      add(q2[t2 - 1] + 1, q2[t2], -b[q2[t2]], 1);
      t2--;
    }
    q1[++t1] = i;
    add(q1[t1 - 1] + 1, q1[t1], -b[q1[t1]], 1);
    q2[++t2] = i;
    add(q2[t2 - 1] + 1, q2[t2], b[q2[t2]], 1);
    if (pe < pre[i] + 1) pe = pre[i] + 1;
    int ld = max(pe, L);
    int ps = find(ld, i, i + k, 1, 0);
    if (i - ps > rr - rl) {
      rl = ps;
      rr = i;
    }
  }
}
int main() {
  int n, d, i, j;
  scanf("%d%d%d", &n, &k, &d);
  for (i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    a[i] += 1000000005;
    pre[i] = lzs[a[i]];
    lzs[a[i]] = i;
    if (d) b[i] = a[i] / d;
  }
  rr = -1;
  if (!d) {
    for (i = 1; i <= n;) {
      for (j = i + 1; j <= n && a[j] == a[i]; j++)
        ;
      if (j - i > rr - rl + 1) {
        rl = i;
        rr = j - 1;
      }
      i = j;
    }
  } else {
    build(1, n, 1);
    for (i = 1; i <= n;) {
      for (j = i + 1; j <= n && a[j] % d == a[i] % d; j++)
        ;
      work(i, j - 1);
      i = j;
    }
  }
  printf("%d %d\n", rl, rr);
  return 0;
}
