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 = 210000;
int n, k, d;
int a[N], b[N];
struct link {
  int l, r, w;
} sma[N], big[N];
int ts, tb;
map<int, int> gt;
int lazy[N * 4];
int mi[N * 4];
void build(int me, int l, int r) {
  if (l == r) {
    mi[me] = -l;
    return;
  }
  int mid = (l + r) >> 1;
  build(me * 2, l, mid);
  build(me * 2 + 1, mid + 1, r);
  mi[me] = min(mi[me * 2], mi[me * 2 + 1]);
}
void down(int me) {
  if (lazy[me] == 0) return;
  for (int i = (0); i <= (int)1; i++) {
    lazy[me * 2 + i] += lazy[me];
    mi[me * 2 + i] += lazy[me];
  }
  lazy[me] = 0;
}
void add(int me, int l, int r, int x, int y, int v) {
  if (l ^ r) down(me);
  if (x <= l && r <= y) {
    lazy[me] += v;
    mi[me] += v;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid) add(me * 2, l, mid, x, y, v);
  if (y > mid) add(me * 2 + 1, mid + 1, r, x, y, v);
  mi[me] = min(mi[me * 2], mi[me * 2 + 1]);
}
int work(int me, int l, int r, int x, int y, int key) {
  if (l ^ r) down(me);
  if (mi[me] > key) return -1;
  if (l == r) return l;
  int mid = (l + r) >> 1;
  int u1 = -1;
  if (y > mid) u1 = work(me * 2 + 1, mid + 1, r, x, y, key);
  if (x <= mid && u1 == -1) u1 = work(me * 2, l, mid, x, y, key);
  return u1;
}
int main() {
  scanf("%d%d%d", &n, &k, &d);
  for (int i = (1); i <= (int)n; i++) scanf("%d", &a[i]);
  if (!d) {
    int ans = 0;
    int L, R;
    for (int i = (1); i <= (int)n; i++) {
      int j = i;
      while (j < n && a[j + 1] == a[i]) j++;
      if (j - i + 1 > ans) {
        L = i;
        R = j;
        ans = j - i + 1;
      }
      i = j;
    }
    printf("%d %d\n", L, R);
    return 0;
  }
  for (int i = (1); i <= (int)n; i++) b[i] = ((a[i] % d) + d) % d;
  build(1, 1, n);
  int ans = 0;
  for (int i = (1); i <= (int)n; i++) a[i] = (a[i] - b[i]) / d;
  int Ri = n;
  int L, R;
  for (int i = (n); i >= (int)1; i--) {
    if ((i ^ n) && b[i] != b[i + 1]) Ri = i;
    if (gt.find(a[i]) != gt.end()) Ri = min(Ri, gt[a[i]] - 1);
    gt[a[i]] = i;
    while (ts && sma[ts].w >= a[i]) {
      add(1, 1, n, sma[ts].l, sma[ts].r, sma[ts].w);
      ts--;
    }
    link now;
    now.l = i;
    if (!ts)
      now.r = n;
    else
      now.r = sma[ts].l - 1;
    now.w = a[i];
    sma[++ts] = now;
    add(1, 1, n, now.l, now.r, -now.w);
    while (tb && big[tb].w <= a[i]) {
      add(1, 1, n, big[tb].l, big[tb].r, -big[tb].w);
      tb--;
    }
    now.l = i;
    if (!tb)
      now.r = n;
    else
      now.r = big[tb].l - 1;
    now.w = a[i];
    big[++tb] = now;
    add(1, 1, n, now.l, now.r, now.w);
    int id = work(1, 1, n, i, Ri, k - i);
    if (id == -1) continue;
    if (id - i + 1 >= ans) {
      ans = id - i + 1;
      L = i;
      R = id;
    }
  }
  printf("%d %d\n", L, R);
  return 0;
}
