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;
long long n, k, d, num[200007], res[2] = {1, 0}, st1[200007], st2[200007], tp1,
                                tp2;
long long t[800007], tag[800007];
map<long long, long long> lst;
long long read() {
  long long num = 0, f = 1;
  char c = getchar();
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') f = -1, c = getchar();
  while (c >= '0' && c <= '9') num = num * 10 + c - '0', c = getchar();
  return num * f;
}
long long mtree(long long w, long long l, long long r) {
  t[w] = 1e9;
  tag[w] = 0;
  if (l == r) return 0;
  long long mid = (l + r) / 2;
  mtree(2 * w, l, mid);
  mtree(2 * w + 1, mid + 1, r);
  return 0;
}
long long down(long long w) {
  if (!tag[w]) return 0;
  t[2 * w] += tag[w];
  t[2 * w + 1] += tag[w];
  tag[2 * w] += tag[w];
  tag[2 * w + 1] += tag[w];
  tag[w] = 0;
  return 0;
}
long long reset(long long w, long long l, long long r, long long x) {
  if (l == r) {
    t[w] = l;
    return 0;
  }
  down(w);
  long long mid = (l + r) / 2;
  if (x <= mid)
    reset(2 * w, l, mid, x);
  else
    reset(2 * w + 1, mid + 1, r, x);
  t[w] = min(t[2 * w], t[2 * w + 1]);
  return 0;
}
long long change(long long w, long long l, long long r, long long x,
                 long long y, long long v) {
  if (x <= l && r <= y) {
    t[w] += v;
    tag[w] += v;
    return 0;
  }
  down(w);
  long long mid = (l + r) / 2;
  if (x <= mid) change(2 * w, l, mid, x, y, v);
  if (y > mid) change(2 * w + 1, mid + 1, r, x, y, v);
  t[w] = min(t[2 * w], t[2 * w + 1]);
  return 0;
}
long long ask(long long w, long long l, long long r, long long v) {
  if (l == r) return l;
  down(w);
  long long mid = (l + r) / 2;
  if (t[2 * w] <= v)
    return ask(2 * w, l, mid, v);
  else
    return ask(2 * w + 1, mid + 1, r, v);
}
long long solve(long long l, long long r) {
  lst.clear();
  mtree(1, l, r);
  st1[0] = st2[0] = l - 1;
  tp1 = tp2 = 0;
  for (long long i = l; i <= r; i++) {
    reset(1, l, r, i);
    while (tp1 && num[st1[tp1]] >= num[i]) {
      change(1, l, r, st1[tp1 - 1] + 1, st1[tp1], num[st1[tp1]] / d);
      tp1--;
    }
    st1[++tp1] = i;
    change(1, l, r, st1[tp1 - 1] + 1, i, -num[i] / d);
    while (tp2 && num[st2[tp2]] <= num[i]) {
      change(1, l, r, st2[tp2 - 1] + 1, st2[tp2], -num[st2[tp2]] / d);
      tp2--;
    }
    st2[++tp2] = i;
    change(1, l, r, st2[tp2 - 1] + 1, i, num[i] / d);
    if (lst.count(num[i])) change(1, l, r, l, lst[num[i]], 1e9);
    lst[num[i]] = i;
    if (t[1] > i + k) continue;
    long long ans = ask(1, l, r, i + k);
    if (i - ans > res[1] - res[0] ||
        (i - ans == res[1] - res[0] && ans < res[0]))
      res[0] = ans, res[1] = i;
  }
  return 0;
}
signed main() {
  n = read();
  k = read();
  d = read();
  for (long long i = 1; i <= n; i++) num[i] = read();
  if (d == 0) {
    for (long long i = 1, j; i <= n; i = j) {
      j = i;
      while (j <= n && num[j] == num[i]) j++;
      if (j - i > res[1] - res[0] + 1 ||
          (j - i == res[1] - res[0] + 1 && i < res[0]))
        res[0] = i, res[1] = j - 1;
    }
    cout << res[0] << ' ' << res[1] << endl;
    return 0;
  }
  for (long long i = 1, j; i <= n; i = j) {
    j = i;
    while (j <= n && (num[j] % d + d) % d == (num[i] % d + d) % d) j++;
    solve(i, j - 1);
  }
  cout << res[0] << ' ' << res[1] << endl;
  return 0;
}
