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 gi() {
  char c;
  int num = 0, flg = 1;
  while ((c = getchar()) < '0' || c > '9')
    if (c == '-') flg = -1;
  while (c >= '0' && c <= '9') {
    num = num * 10 + c - 48;
    c = getchar();
  }
  return num * flg;
}
const int INF = 1000000000;
long long a[200005];
map<long long, int> last;
struct node {
  int l, r;
  long long la, x;
} t[200005 << 2];
int sl[200005], topl, sr[200005], topr;
void cal(int i, long long k) {
  t[i].la += k;
  t[i].x += k;
}
void pushdown(int i) {
  if (t[i].la && t[i].l < t[i].r) {
    cal(i << 1, t[i].la);
    cal(i << 1 | 1, t[i].la);
    t[i].la = 0;
  }
}
void build(int i, int l, int r) {
  t[i].l = l;
  t[i].r = r;
  if (l == r) {
    t[i].x = l;
    return;
  }
  int mid = (l + r) >> 1;
  build(i << 1, l, mid);
  build(i << 1 | 1, mid + 1, r);
  t[i].x = min(t[i << 1].x, t[i << 1 | 1].x);
}
void insert(int i, int l, int r, long long k) {
  if (t[i].l > r || t[i].r < l) return;
  pushdown(i);
  if (l <= t[i].l && t[i].r <= r) {
    cal(i, k);
    return;
  }
  insert(i << 1, l, r, k);
  insert(i << 1 | 1, l, r, k);
  t[i].x = min(t[i << 1].x, t[i << 1 | 1].x);
}
bool flg;
int ans;
int EF(int i, int k) {
  if (t[i].l == t[i].r) return t[i].l;
  pushdown(i);
  if (t[i << 1].x <= k)
    return EF(i << 1, k);
  else
    return EF(i << 1 | 1, k);
}
void query(int i, int l, int r, int k) {
  if (t[i].l > r || t[i].r < l) return;
  pushdown(i);
  if (l <= t[i].l && t[i].r <= r) {
    if (t[i].x <= k) flg = 1, ans = EF(i, k);
    return;
  }
  if (!flg) query(i << 1, l, r, k);
  if (!flg) query(i << 1 | 1, l, r, k);
}
void del(int i, int x) {
  if (x < t[i].l || x > t[i].r) return;
  pushdown(i);
  if (t[i].l == x && t[i].r == x) {
    t[i].x = 0;
    return;
  }
  del(i << 1, x);
  del(i << 1 | 1, x);
  t[i].x = min(t[i << 1].x, t[i << 1 | 1].x);
}
void print(int i) {
  if (t[i].l == t[i].r) {
    printf("%lld ", t[i].x);
    return;
  }
  pushdown(i);
  print(i << 1);
  print(i << 1 | 1);
}
int main() {
  int n, k, d, i, L, al = 1, ar = 1;
  n = gi();
  k = gi();
  d = gi();
  for (i = 1; i <= n; i++) a[i] = gi() + 1ll * INF;
  if (d == 0) {
    for (i = 1; i <= n; i++) {
      int tl = i;
      while (a[i] == a[i + 1]) i++;
      if (i - tl > ar - al) al = tl, ar = i;
    }
    printf("%d %d", al, ar);
    return 0;
  }
  build(1, 1, n);
  for (i = L = 1; i <= n; i++) {
    int tmp = L;
    if (a[i] % d == a[i - 1] % d)
      L = max(L, last[a[i]] + 1);
    else
      L = i;
    last[a[i]] = i;
    while (tmp < L) del(1, tmp++);
    while (topl && sl[topl] >= L && a[sl[topl]] >= a[i]) {
      insert(1, max(L, sl[topl - 1] + 1), sl[topl], a[sl[topl]] / d);
      topl--;
    }
    insert(1, max(L, sl[topl] + 1), i, -a[i] / d);
    sl[++topl] = i;
    while (topr && sr[topr] >= L && a[sr[topr]] <= a[i]) {
      insert(1, max(L, sr[topr - 1] + 1), sr[topr], -a[sr[topr]] / d);
      topr--;
    }
    insert(1, max(L, sr[topr] + 1), i, a[i] / d);
    sr[++topr] = i;
    flg = 0;
    ans = 0;
    query(1, L, i, k + i);
    if (ar - al < i - ans) al = ans, ar = i;
  }
  printf("%d %d", al, ar);
}
