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;
struct seg_tree {
  int sign[210000 * 4], minn[210000 * 4];
  void add(int p, int l, int r, int x, int y, int k) {
    int mid = (l + r) / 2;
    if (x <= l && y >= r) {
      sign[p] += k;
      minn[p] += k;
      return;
    }
    if (x <= mid) add(p * 2, l, mid, x, y, k);
    if (y > mid) add(p * 2 + 1, mid + 1, r, x, y, k);
    minn[p] = min(minn[p * 2], minn[p * 2 + 1]) + sign[p];
  }
  int calc(int p, int l, int r, int k) {
    int mid = (l + r) / 2;
    if (l == r) return l;
    k -= sign[p];
    if (minn[p * 2] <= k) return calc(p * 2, l, mid, k);
    return calc(p * 2 + 1, mid + 1, r, k);
  }
} T;
int ans1, ans2, ans, n, m, d, a[210000], last, i, sta1[210000], sta2[210000],
    n1, n2;
map<int, int> Map;
int main() {
  scanf("%d%d%d", &n, &m, &d);
  for (i = 1; i <= n; ++i) scanf("%d", &a[i]), a[i] += 1e9 + 1;
  if (!d) {
    for (i = 1; i <= n; ++i) {
      if (i == 1 || a[i] != a[i - 1]) last = i;
      if (i - last + 1 > ans) ans = i - last + 1, ans1 = last, ans2 = i;
    }
  } else {
    T.add(1, 1, n, 1, n, 1100000);
    for (i = 1; i <= n; ++i) {
      if (i != 1 && (a[i] - a[i - 1]) % d) {
        T.add(1, 1, n, last + 1, i - 1, 1100000);
        last = i - 1;
      }
      if (Map[a[i]] > last) {
        T.add(1, 1, n, last + 1, Map[a[i]], 1100000);
        last = Map[a[i]];
      }
      Map[a[i]] = i;
      while (n1 > 0 && a[i] > a[sta1[n1]]) {
        T.add(1, 1, n, sta1[n1 - 1] + 1, sta1[n1], a[i] / d - a[sta1[n1]] / d);
        --n1;
      }
      while (n2 > 0 && a[i] < a[sta2[n2]]) {
        T.add(1, 1, n, sta2[n2 - 1] + 1, sta2[n2], a[sta2[n2]] / d - a[i] / d);
        --n2;
      }
      sta1[++n1] = sta2[++n2] = i;
      T.add(1, 1, n, i, i, -1100000 + i);
      int tmp = T.calc(1, 1, n, i + m);
      if (i - tmp + 1 > ans) {
        ans = i - tmp + 1;
        ans1 = tmp;
        ans2 = i;
      }
    }
  }
  printf("%d %d\n", ans1, ans2);
}
