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;
map<long long, long long> pos;
long long Id;
const long long maxn = 3e6;
long long n, k, d, a[maxn + 5], b[maxn + 5];
long long sta1[maxn + 5], top1, sta2[maxn + 5], top2, Rp[maxn + 5];
long long mn[maxn + 5], tag[maxn + 5];
long long ansl, ansr, anslen;
void push(long long p) {
  mn[p + p] += tag[p];
  tag[p + p] += tag[p];
  mn[p + p + 1] += tag[p];
  tag[p + p + 1] += tag[p];
  tag[p] = 0;
}
void build(long long p, long long l, long long r) {
  tag[p] = 0;
  if (l == r) {
    mn[p] = -l;
    return;
  }
  long long mid = (l + r) >> 1;
  build(p + p, l, mid), build(p + p + 1, mid + 1, r);
  mn[p] = min(mn[p + p], mn[p + p + 1]);
}
void modify(long long p, long long l, long long r, long long ql, long long qr,
            long long d) {
  if (ql > qr) return;
  if (l == ql && r == qr) {
    mn[p] += d;
    tag[p] += d;
    return;
  }
  push(p);
  long long mid = (l + r) >> 1;
  if (qr <= mid)
    modify(p + p, l, mid, ql, qr, d);
  else if (mid < ql)
    modify(p + p + 1, mid + 1, r, ql, qr, d);
  else
    modify(p + p, l, mid, ql, mid, d),
        modify(p + p + 1, mid + 1, r, mid + 1, qr, d);
  mn[p] = min(mn[p + p + 1], mn[p + p]);
}
long long query(long long p, long long l, long long r, long long d) {
  push(p);
  if (l == r) return l;
  long long mid = (l + r) >> 1;
  if (mn[p + p + 1] <= d)
    return query(p + p + 1, mid + 1, r, d);
  else
    return query(p + p, l, mid, d);
}
void solve(long long l, long long r) {
  long long len = r - l + 1;
  build(1, 1, len);
  top1 = 0, top2 = 0;
  Rp[r] = r + 1;
  for (long long i = r - 1; i >= l; i--) Rp[i] = min(Rp[i], Rp[i + 1]);
  for (long long i = l; i <= r; i++) {
    b[i] = a[i];
    a[i] /= d;
  }
  for (long long i = r; i >= l; i--) {
    while (top1 >= 1 && a[sta1[top1]] <= a[i]) {
      long long tp = sta1[top1];
      top1--;
      if (top1 == 0)
        modify(1, 1, len, tp - l + 1, len, -a[tp]);
      else
        modify(1, 1, len, tp - l + 1, sta1[top1] - l, -a[tp]);
    }
    sta1[++top1] = i;
    if (top1 == 1)
      modify(1, 1, len, i - l + 1, len, a[i]);
    else
      modify(1, 1, len, i - l + 1, sta1[top1 - 1] - l, a[i]);
    while (top2 >= 1 && a[sta2[top2]] >= a[i]) {
      long long tp = sta2[top2];
      top2--;
      if (top2 == 0)
        modify(1, 1, len, tp - l + 1, len, a[tp]);
      else
        modify(1, 1, len, tp - l + 1, sta2[top2] - l, a[tp]);
    }
    sta2[++top2] = i;
    if (top2 == 1)
      modify(1, 1, len, i - l + 1, len, -a[i]);
    else
      modify(1, 1, len, i - l + 1, sta2[top2 - 1] - l, -a[i]);
    if (i - l >= 1) modify(1, 1, len, 1, i - l, 1e15);
    if (Rp[i] - l + 1 <= len) modify(1, 1, len, Rp[i] - l + 1, len, 1e15);
    long long p = query(1, 1, len, k - (i - l + 1)) + l - 1;
    if (p >= i) {
      if (p - i + 1 >= anslen) {
        anslen = p - i + 1;
        ansl = i, ansr = p;
      }
    }
    if (i - l >= 1) modify(1, 1, len, 1, i - l, -1e15);
    if (Rp[i] - l + 1 <= len) modify(1, 1, len, Rp[i] - l + 1, len, -1e15);
  }
  for (long long i = l; i <= r; i++) a[i] = b[i];
}
signed main() {
  scanf("%lld %lld %lld", &n, &k, &d);
  for (long long i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    a[i] += 1e9;
    pos[a[i]] = n + 1;
  }
  if (d == 0) {
    long long rp = 1;
    for (long long i = 1; i <= n; i++) {
      rp = max(rp, i);
      while (rp <= n && a[rp] == a[i]) rp++;
      if (rp - i > anslen) {
        ansr = rp - 1;
        ansl = i;
        anslen = rp - i;
      }
    }
    printf("%lld %lld\n", ansl, ansr);
    return 0;
  }
  for (long long i = n; i >= 1; i--) {
    Rp[i] = pos[a[i]];
    pos[a[i]] = i;
  }
  long long R = n;
  for (long long i = n; i >= 1; i--) {
    while (R >= i && a[R] % d != a[i] % d) {
      R--;
    }
    if (i == 1 or a[i - 1] % d != a[R] % d) solve(i, R);
  }
  printf("%lld %lld\n", ansl, ansr);
  return 0;
}
