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<int, int> mp;
int f[210000 * 4], mn[210000 * 4];
void add(int u, int L, int R, int l, int r, int k) {
  l = max(l, L);
  r = min(r, R);
  if (l >= r) return;
  if (l == L && R == r) {
    mn[u] += k;
    f[u] += k;
    return;
  }
  add(u * 2, L, ((L + R) >> 1), l, r, k);
  add(u * 2 + 1, ((L + R) >> 1), R, l, r, k);
  mn[u] = min(mn[u * 2], mn[u * 2 + 1]) + f[u];
}
int calc(int u, int L, int R, int k) {
  if (L + 1 == R) return L;
  k -= f[u];
  if (mn[u * 2] <= k) return calc(u * 2, L, ((L + R) >> 1), k);
  return calc(u * 2 + 1, ((L + R) >> 1), R, k);
}
int sa[210000], sb[210000], na, nb, a[210000];
int ans, st, ed;
int i, last, n, m, d;
int main() {
  scanf("%d%d%d", &n, &m, &d);
  for (int i = (1); i < (n + 1); i++) scanf("%d", a + i);
  if (!d) {
    for (int i = (1); i < (n + 1); i++) {
      if (i == 1 || a[i] != a[i - 1]) last = i;
      if (ans < i - last + 1) ans = i - last + 1, st = last, ed = i;
    }
  } else {
    for (int i = (1); i < (n + 1); i++) {
      if (i != 1 && (a[i] - a[i - 1]) % d) {
        add(1, 1, n + 1, last + 1, i, 1100000);
        last = i - 1;
      }
      if (mp[a[i]] > last) {
        add(1, 1, n + 1, last + 1, mp[a[i]] + 1, 1100000);
        last = mp[a[i]];
      }
      mp[a[i]] = i;
      while (na && a[i] > a[sa[na]]) {
        add(1, 1, n + 1, sa[na - 1] + 1, sa[na] + 1, (a[i] - a[sa[na]]) / d);
        na--;
      }
      while (nb && a[i] < a[sb[nb]]) {
        add(1, 1, n + 1, sb[nb - 1] + 1, sb[nb] + 1, (a[sb[nb]] - a[i]) / d);
        nb--;
      }
      sa[++na] = sb[++nb] = i;
      add(1, 1, n + 1, i, i + 1, i);
      int tmp = calc(1, 1, n + 1, i + m);
      if (i - tmp + 1 > ans) {
        ans = i - tmp + 1;
        st = tmp;
        ed = i;
      }
    }
  }
  printf("%d %d\n", st, ed);
  return 0;
}
