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;
bool debug = 1;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
long long ln, lk, lm;
int a[200105], d;
void cal() {
  int p[200105] = {0};
  int mm = 0;
  for (int i = 2; i <= n; i++) {
    if (a[i] == a[i - 1]) p[i] = p[i - 1] + 1;
    mm = max(mm, p[i]);
  }
  for (int(i) = 1; (i) <= (int)(n); (i)++)
    if (p[i] == mm) {
      printf("%d %d\n", i - mm, i);
      exit(0);
    }
}
map<int, int> mp;
int L, R;
int lz[200105 * 4], t[200105 * 4], sta1[200105], sta2[200105], n1, n2;
void update(int rt, int l, int r, int L, int R, int v) {
  if (L <= l && r <= R) {
    lz[rt] += v;
    t[rt] += v;
    return;
  }
  int mid = (l + r) / 2;
  if (L <= mid) update((rt << 1), l, mid, L, R, v);
  if (mid < R) update((rt << 1 | 1), mid + 1, r, L, R, v);
  t[rt] = min(t[(rt << 1)], t[(rt << 1 | 1)]) + lz[rt];
}
int qy(int rt, int l, int r, int k) {
  if (l == r) return r;
  int mid = (l + r) / 2;
  k -= lz[rt];
  if (t[(rt << 1)] <= k)
    return qy((rt << 1), l, mid, k);
  else
    return qy((rt << 1 | 1), mid + 1, r, k);
}
int main() {
  scanf("%d%d%d", &n, &k, &d);
  for (int(i) = 1; (i) <= (int)(n); (i)++) scanf("%d", a + i);
  if (d == 0) cal();
  L = 1;
  R = 1;
  for (int i = 1, l = 0; i <= n; i++) {
    if (i != 1 && (a[i] - a[i - 1]) % d != 0) {
      update(1, 1, n, l + 1, i - 1, (1000005));
      l = i - 1;
    }
    if (mp[a[i]] > l) {
      update(1, 1, n, l + 1, mp[a[i]], (1000005));
      l = mp[a[i]];
    }
    mp[a[i]] = i;
    while (n1 && a[i] > a[sta1[n1]]) {
      update(1, 1, n, sta1[n1 - 1] + 1, sta1[n1], a[i] / d - a[sta1[n1]] / d);
      n1--;
    }
    while (n2 && a[i] < a[sta2[n2]]) {
      update(1, 1, n, sta2[n2 - 1] + 1, sta2[n2], a[sta2[n2]] / d - a[i] / d);
      n2--;
    }
    sta1[++n1] = i;
    sta2[++n2] = i;
    update(1, 1, n, i, i, i);
    int tmp = qy(1, 1, n, i + k);
    if (i - tmp > R - L) {
      L = tmp;
      R = i;
    }
  }
  printf("%d %d\n", L, R);
  return 0;
}
