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;
int n, m, d, i, j, k, ansl, ansr, ll, rr, lim, tmp;
int a[200005];
long long Min[800005], add[800005], val;
int st1[200005], stl1[200005], str1[200005], top1;
int st2[200005], stl2[200005], str2[200005], top2;
map<int, int> pre;
void ans_update(int l, int r) {
  if (r - l < ansr - ansl) return;
  if (r - l > ansr - ansl) {
    ansl = l;
    ansr = r;
    return;
  }
  if (l < ansl) ansl = l, ansr = r;
}
void down(int x) {
  add[x << 1] += add[x];
  Min[x << 1] += add[x];
  add[x << 1 | 1] += add[x];
  Min[x << 1 | 1] += add[x];
  add[x] = 0;
}
void C(int x, int l, int r) {
  if (l >= ll && r <= rr) {
    add[x] += val;
    Min[x] += val;
    return;
  }
  int mid = l + r >> 1;
  if (add[x]) down(x);
  if (rr <= mid)
    C(x << 1, l, mid);
  else if (ll > mid)
    C(x << 1 | 1, mid + 1, r);
  else
    C(x << 1, l, mid), C(x << 1 | 1, mid + 1, r);
  if (Min[x << 1] < Min[x << 1 | 1])
    Min[x] = Min[x << 1];
  else
    Min[x] = Min[x << 1 | 1];
}
void Q(int x, int l, int r) {
  if (Min[x] > 0 || tmp) return;
  if (l >= ll && r <= rr) {
    if (l == r) {
      tmp = l;
      return;
    }
    int mid = l + r >> 1;
    if (add[x]) down(x);
    Q(x << 1, l, mid);
    Q(x << 1 | 1, mid + 1, r);
    return;
  }
  int mid = l + r >> 1;
  if (add[x]) down(x);
  if (rr <= mid)
    Q(x << 1, l, mid);
  else if (ll > mid)
    Q(x << 1 | 1, mid + 1, r);
  else
    Q(x << 1, l, mid), Q(x << 1 | 1, mid + 1, r);
}
int main() {
  ansl = 1;
  ansr = 0;
  scanf("%d%d%d", &n, &m, &d);
  for (i = 1; i <= n; ++i) scanf("%d", &a[i]);
  if (d == 0) {
    for (i = k = 1; i <= n; ++i) {
      if (a[i] != a[k]) k = i;
      ans_update(k, i);
    }
    printf("%d %d\n", ansl, ansr);
    return 0;
  }
  ll = 1;
  rr = n;
  val = -(long long)m * d;
  C(1, 1, n);
  lim = 1;
  for (i = 1; i <= n; ++i) {
    k = pre[a[i]];
    if (k + 1 > lim) lim = k + 1;
    pre[a[i]] = i;
    if (i > 1 && (a[i] - a[i - 1]) % d != 0) lim = i;
    for (; top1 && st1[top1] >= a[i]; --top1) {
      ll = stl1[top1];
      rr = str1[top1];
      val = st1[top1];
      C(1, 1, n);
    }
    st1[++top1] = a[i];
    stl1[top1] = str1[top1 - 1] + 1;
    str1[top1] = i;
    ll = stl1[top1];
    rr = str1[top1];
    val = -st1[top1];
    C(1, 1, n);
    for (; top2 && st2[top2] <= a[i]; --top2) {
      ll = stl2[top2];
      rr = str2[top2];
      val = -st2[top2];
      C(1, 1, n);
    }
    st2[++top2] = a[i];
    stl2[top2] = str2[top2 - 1] + 1;
    str2[top2] = i;
    ll = stl2[top2];
    rr = str2[top2];
    val = st2[top2];
    C(1, 1, n);
    tmp = 0;
    ll = lim;
    rr = i;
    Q(1, 1, n);
    ans_update(tmp, i);
    ll = 1;
    rr = i;
    val = -d;
    C(1, 1, n);
  }
  printf("%d %d\n", ansl, ansr);
}
